-- |
-- Module:     Data.Vector.Algorithms.FixedSort
-- Copyright:  (c) Sergey Vinokurov 2023
-- License:    Apache-2.0 (see LICENSE)
-- Maintainer: serg.foo@gmail.com
--
-- Sorts for fixed number of elements. Mostly helpers for quicksort

module Data.Vector.Algorithms.FixedSort
  ( sort3
  , sort4
  , bitonicSort
  ) where

import Control.Monad hiding (forM)
import Control.Monad.Primitive
import Data.Vector.Generic.Mutable qualified as GM

{-# INLINABLE sort3 #-}
-- | Sorts the elements at the three given indices. The indices are assumed
-- to be given from lowest to highest, so if 'l < m < u' then
-- 'sort3ByIndex cmp a m l u' essentially sorts the median of three into the
-- lowest position in the array.
sort3
  :: (PrimMonad m, GM.MVector v a, Ord a)
  => v (PrimState m) a -> m ()
sort3 :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a, Ord a) =>
v (PrimState m) a -> m ()
sort3 !v (PrimState m) a
xs = do
  !a
x0 <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
GM.unsafeRead v (PrimState m) a
xs Int
0
  !a
x1 <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
GM.unsafeRead v (PrimState m) a
xs Int
1
  !a
x2 <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
GM.unsafeRead v (PrimState m) a
xs Int
2
  if a
x1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
  then
    if a
x2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
    then
      if a
x2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
      then do
        v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x2
        v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x0
      else do
         v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x1
         v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x2
         v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x0
    else do
      v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x1
      v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x0
  else
    if a
x2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
    then
      if a
x2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
      then do
        v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x2
        v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x0
        v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x1
      else do
        v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x2
        v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x1
    else
      () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()

{-# INLINABLE sort4 #-}
-- | Sorts the elements at the four given indices. Like the 2 and 3 element
-- versions, this assumes that the indices are given in increasing order, so
-- it can be used to sort medians into particular positions and so on.
sort4
  :: (PrimMonad m, GM.MVector v a, Ord a)
  => v (PrimState m) a -> m ()
sort4 :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a, Ord a) =>
v (PrimState m) a -> m ()
sort4 !v (PrimState m) a
xs = do
  !a
x0 <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
GM.unsafeRead v (PrimState m) a
xs Int
0
  !a
x1 <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
GM.unsafeRead v (PrimState m) a
xs Int
1
  !a
x2 <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
GM.unsafeRead v (PrimState m) a
xs Int
2
  !a
x3 <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
GM.unsafeRead v (PrimState m) a
xs Int
3
  if a
x1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
  then
    if a
x2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
    then
      if a
x2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
      then
        if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
        then
          if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x2
          then do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x1
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x0
          else do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x1
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x0
        else
          if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
          then do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x2
            -- GM.unsafeWrite xs 1 x1
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x0
          else do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x2
            -- GM.unsafeWrite xs 1 x1
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x0
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x3
      else
        if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x2
        then
          if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
          then do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x3
            -- GM.unsafeWrite xs 1 x1
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x0
          else do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x1
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x0
        else
          if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
          then do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x1
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x0
          else do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x1
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x0
            -- GM.unsafeWrite xs 3 x3
    else
      if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
      then
        if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
        then do
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x3
          -- GM.unsafeWrite xs 1 x1
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x0
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x2
        else do
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x1
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x3
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x0
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x2
      else
        if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x2
        then do
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x1
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x0
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x3
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x2
        else do
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x1
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x0
          -- GM.unsafeWrite xs 2 x2
          -- GM.unsafeWrite xs 3 x3
  else
    if a
x2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
    then
      if a
x2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
      then
        if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
        then
          if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x2
          then do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x0
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x1
          else do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x0
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x1
        else
          if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
          then do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x0
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x1
          else do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x0
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x1
            -- GM.unsafeWrite xs 3 x3
      else
        if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x2
        then
          if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
          then do
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x0
            -- GM.unsafeWrite xs 2 x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x1
          else do
            -- GM.unsafeWrite xs 0 x0
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x3
            -- GM.unsafeWrite xs 2 x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x1
        else
          if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
          then do
            -- GM.unsafeWrite xs 0 x0
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x3
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x1
          else do
            -- GM.unsafeWrite xs 0 x0
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x2
            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x1
            -- GM.unsafeWrite xs 3 x3
    else
      if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x1
      then
        if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x0
        then do
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
0 a
x3
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x0
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x1
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x2
        else do
          -- GM.unsafeWrite xs 0 x0
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
1 a
x3
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x1
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x2
      else
        if a
x3 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x2
        then do
          -- GM.unsafeWrite xs 0 x0
          -- GM.unsafeWrite xs 1 x1
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
2 a
x3
          v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
xs Int
3 a
x2
        else do
          -- GM.unsafeWrite xs 0 x0
          -- GM.unsafeWrite xs 1 x1
          -- GM.unsafeWrite xs 2 x2
          -- GM.unsafeWrite xs 3 x3
          () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()

{-# INLINABLE bitonicSort #-}
-- | Sorts vectors containing strictly less that 17 elements. Otherwise does nothing.
--
-- Depending on GHC may be good candidate for SPECIALIZE pragma.
bitonicSort
  :: forall m v a. (PrimMonad m, Ord a, GM.MVector v a)
  => Int               -- ^ Vector length
  -> v (PrimState m) a -- ^ Vector to be sorted
  -> m ()
bitonicSort :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, Ord a, MVector v a) =>
Int -> v (PrimState m) a -> m ()
bitonicSort !Int
n !v (PrimState m) a
v = do
  case Int
n of
    Int
2  ->
      Int -> Int -> m ()
swap Int
0 Int
1
    Int
3  ->
      -- swap 1 2
      -- swap 0 2
      -- swap 0 1
      v (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a, Ord a) =>
v (PrimState m) a -> m ()
sort3 v (PrimState m) a
v
    Int
4  ->
      -- swap 0 1
      -- swap 2 3
      -- swap 0 2
      -- swap 1 3
      -- swap 1 2
      v (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a, Ord a) =>
v (PrimState m) a -> m ()
sort4 v (PrimState m) a
v
    Int
5  -> do
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
0 Int
3
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
1 Int
2
    Int
6  -> do
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
2 Int
5
      Int -> Int -> m ()
swap Int
0 Int
3
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
2 Int
3
    Int
7  -> do
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
0 Int
4
      Int -> Int -> m ()
swap Int
1 Int
5
      Int -> Int -> m ()
swap Int
0 Int
3
      Int -> Int -> m ()
swap Int
2 Int
5
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
2 Int
3
    Int
8  -> do
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
5 Int
7
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
0 Int
4
      Int -> Int -> m ()
swap Int
3 Int
7
      Int -> Int -> m ()
swap Int
1 Int
5
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
3 Int
6
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
3 Int
4
    Int
9  -> do
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
7 Int
8
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
2 Int
5
      Int -> Int -> m ()
swap Int
0 Int
3
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
5 Int
8
      Int -> Int -> m ()
swap Int
3 Int
6
      Int -> Int -> m ()
swap Int
4 Int
7
      Int -> Int -> m ()
swap Int
2 Int
5
      Int -> Int -> m ()
swap Int
0 Int
3
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
5 Int
7
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
2 Int
3
    Int
10 -> do
      Int -> Int -> m ()
swap Int
4 Int
9
      Int -> Int -> m ()
swap Int
3 Int
8
      Int -> Int -> m ()
swap Int
2 Int
7
      Int -> Int -> m ()
swap Int
1 Int
6
      Int -> Int -> m ()
swap Int
0 Int
5
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
6 Int
9
      Int -> Int -> m ()
swap Int
0 Int
3
      Int -> Int -> m ()
swap Int
5 Int
8
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
3 Int
6
      Int -> Int -> m ()
swap Int
7 Int
9
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
5 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
7 Int
8
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
2 Int
5
      Int -> Int -> m ()
swap Int
6 Int
8
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
4 Int
7
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
4 Int
5
    Int
11 -> do
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
5 Int
7
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
8 Int
10
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
9 Int
10
      Int -> Int -> m ()
swap Int
0 Int
4
      Int -> Int -> m ()
swap Int
3 Int
7
      Int -> Int -> m ()
swap Int
1 Int
5
      Int -> Int -> m ()
swap Int
6 Int
10
      Int -> Int -> m ()
swap Int
4 Int
8
      Int -> Int -> m ()
swap Int
5 Int
9
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
0 Int
4
      Int -> Int -> m ()
swap Int
3 Int
8
      Int -> Int -> m ()
swap Int
1 Int
5
      Int -> Int -> m ()
swap Int
6 Int
10
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
7 Int
10
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
6 Int
8
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
7 Int
9
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
7 Int
8
    Int
12 -> do
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
10 Int
11
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
5 Int
7
      Int -> Int -> m ()
swap Int
9 Int
11
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
8 Int
10
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
9 Int
10
      Int -> Int -> m ()
swap Int
0 Int
4
      Int -> Int -> m ()
swap Int
7 Int
11
      Int -> Int -> m ()
swap Int
1 Int
5
      Int -> Int -> m ()
swap Int
6 Int
10
      Int -> Int -> m ()
swap Int
3 Int
7
      Int -> Int -> m ()
swap Int
4 Int
8
      Int -> Int -> m ()
swap Int
5 Int
9
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
0 Int
4
      Int -> Int -> m ()
swap Int
7 Int
11
      Int -> Int -> m ()
swap Int
3 Int
8
      Int -> Int -> m ()
swap Int
1 Int
5
      Int -> Int -> m ()
swap Int
6 Int
10
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
7 Int
10
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
6 Int
8
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
7 Int
9
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
7 Int
8
    Int
13 -> do
      Int -> Int -> m ()
swap Int
1 Int
7
      Int -> Int -> m ()
swap Int
9 Int
11
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
5 Int
8
      Int -> Int -> m ()
swap Int
0 Int
12
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
8 Int
11
      Int -> Int -> m ()
swap Int
7 Int
12
      Int -> Int -> m ()
swap Int
5 Int
9
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
3 Int
7
      Int -> Int -> m ()
swap Int
10 Int
11
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
6 Int
12
      Int -> Int -> m ()
swap Int
7 Int
8
      Int -> Int -> m ()
swap Int
11 Int
12
      Int -> Int -> m ()
swap Int
4 Int
9
      Int -> Int -> m ()
swap Int
6 Int
10
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
10 Int
11
      Int -> Int -> m ()
swap Int
1 Int
7
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
9 Int
11
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
4 Int
7
      Int -> Int -> m ()
swap Int
8 Int
10
      Int -> Int -> m ()
swap Int
0 Int
5
      Int -> Int -> m ()
swap Int
2 Int
5
      Int -> Int -> m ()
swap Int
6 Int
8
      Int -> Int -> m ()
swap Int
9 Int
10
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
7 Int
8
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
5 Int
6
    Int
14 -> do
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
10 Int
11
      Int -> Int -> m ()
swap Int
12 Int
13
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
8 Int
10
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
5 Int
7
      Int -> Int -> m ()
swap Int
9 Int
11
      Int -> Int -> m ()
swap Int
0 Int
4
      Int -> Int -> m ()
swap Int
8 Int
12
      Int -> Int -> m ()
swap Int
1 Int
5
      Int -> Int -> m ()
swap Int
9 Int
13
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
3 Int
7
      Int -> Int -> m ()
swap Int
0 Int
8
      Int -> Int -> m ()
swap Int
1 Int
9
      Int -> Int -> m ()
swap Int
2 Int
10
      Int -> Int -> m ()
swap Int
3 Int
11
      Int -> Int -> m ()
swap Int
4 Int
12
      Int -> Int -> m ()
swap Int
5 Int
13
      Int -> Int -> m ()
swap Int
5 Int
10
      Int -> Int -> m ()
swap Int
6 Int
9
      Int -> Int -> m ()
swap Int
3 Int
12
      Int -> Int -> m ()
swap Int
7 Int
11
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
4 Int
8
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
7 Int
13
      Int -> Int -> m ()
swap Int
2 Int
8
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
9 Int
10
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
11 Int
13
      Int -> Int -> m ()
swap Int
3 Int
8
      Int -> Int -> m ()
swap Int
7 Int
12
      Int -> Int -> m ()
swap Int
6 Int
8
      Int -> Int -> m ()
swap Int
10 Int
12
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
7 Int
9
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
7 Int
8
      Int -> Int -> m ()
swap Int
9 Int
10
      Int -> Int -> m ()
swap Int
11 Int
12
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
    Int
15 -> do
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
10 Int
11
      Int -> Int -> m ()
swap Int
12 Int
13
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
8 Int
10
      Int -> Int -> m ()
swap Int
12 Int
14
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
5 Int
7
      Int -> Int -> m ()
swap Int
9 Int
11
      Int -> Int -> m ()
swap Int
0 Int
4
      Int -> Int -> m ()
swap Int
8 Int
12
      Int -> Int -> m ()
swap Int
1 Int
5
      Int -> Int -> m ()
swap Int
9 Int
13
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
10 Int
14
      Int -> Int -> m ()
swap Int
3 Int
7
      Int -> Int -> m ()
swap Int
0 Int
8
      Int -> Int -> m ()
swap Int
1 Int
9
      Int -> Int -> m ()
swap Int
2 Int
10
      Int -> Int -> m ()
swap Int
3 Int
11
      Int -> Int -> m ()
swap Int
4 Int
12
      Int -> Int -> m ()
swap Int
5 Int
13
      Int -> Int -> m ()
swap Int
6 Int
14
      Int -> Int -> m ()
swap Int
5 Int
10
      Int -> Int -> m ()
swap Int
6 Int
9
      Int -> Int -> m ()
swap Int
3 Int
12
      Int -> Int -> m ()
swap Int
13 Int
14
      Int -> Int -> m ()
swap Int
7 Int
11
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
4 Int
8
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
7 Int
13
      Int -> Int -> m ()
swap Int
2 Int
8
      Int -> Int -> m ()
swap Int
11 Int
14
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
9 Int
10
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
11 Int
13
      Int -> Int -> m ()
swap Int
3 Int
8
      Int -> Int -> m ()
swap Int
7 Int
12
      Int -> Int -> m ()
swap Int
6 Int
8
      Int -> Int -> m ()
swap Int
10 Int
12
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
7 Int
9
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
7 Int
8
      Int -> Int -> m ()
swap Int
9 Int
10
      Int -> Int -> m ()
swap Int
11 Int
12
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
    Int
16 -> do
      Int -> Int -> m ()
swap Int
0 Int
1
      Int -> Int -> m ()
swap Int
2 Int
3
      Int -> Int -> m ()
swap Int
4 Int
5
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
      Int -> Int -> m ()
swap Int
10 Int
11
      Int -> Int -> m ()
swap Int
12 Int
13
      Int -> Int -> m ()
swap Int
14 Int
15
      Int -> Int -> m ()
swap Int
0 Int
2
      Int -> Int -> m ()
swap Int
4 Int
6
      Int -> Int -> m ()
swap Int
8 Int
10
      Int -> Int -> m ()
swap Int
12 Int
14
      Int -> Int -> m ()
swap Int
1 Int
3
      Int -> Int -> m ()
swap Int
5 Int
7
      Int -> Int -> m ()
swap Int
9 Int
11
      Int -> Int -> m ()
swap Int
13 Int
15
      Int -> Int -> m ()
swap Int
0 Int
4
      Int -> Int -> m ()
swap Int
8 Int
12
      Int -> Int -> m ()
swap Int
1 Int
5
      Int -> Int -> m ()
swap Int
9 Int
13
      Int -> Int -> m ()
swap Int
2 Int
6
      Int -> Int -> m ()
swap Int
10 Int
14
      Int -> Int -> m ()
swap Int
3 Int
7
      Int -> Int -> m ()
swap Int
11 Int
15
      Int -> Int -> m ()
swap Int
0 Int
8
      Int -> Int -> m ()
swap Int
1 Int
9
      Int -> Int -> m ()
swap Int
2 Int
10
      Int -> Int -> m ()
swap Int
3 Int
11
      Int -> Int -> m ()
swap Int
4 Int
12
      Int -> Int -> m ()
swap Int
5 Int
13
      Int -> Int -> m ()
swap Int
6 Int
14
      Int -> Int -> m ()
swap Int
7 Int
15
      Int -> Int -> m ()
swap Int
5 Int
10
      Int -> Int -> m ()
swap Int
6 Int
9
      Int -> Int -> m ()
swap Int
3 Int
12
      Int -> Int -> m ()
swap Int
13 Int
14
      Int -> Int -> m ()
swap Int
7 Int
11
      Int -> Int -> m ()
swap Int
1 Int
2
      Int -> Int -> m ()
swap Int
4 Int
8
      Int -> Int -> m ()
swap Int
1 Int
4
      Int -> Int -> m ()
swap Int
7 Int
13
      Int -> Int -> m ()
swap Int
2 Int
8
      Int -> Int -> m ()
swap Int
11 Int
14
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
9 Int
10
      Int -> Int -> m ()
swap Int
2 Int
4
      Int -> Int -> m ()
swap Int
11 Int
13
      Int -> Int -> m ()
swap Int
3 Int
8
      Int -> Int -> m ()
swap Int
7 Int
12
      Int -> Int -> m ()
swap Int
6 Int
8
      Int -> Int -> m ()
swap Int
10 Int
12
      Int -> Int -> m ()
swap Int
3 Int
5
      Int -> Int -> m ()
swap Int
7 Int
9
      Int -> Int -> m ()
swap Int
3 Int
4
      Int -> Int -> m ()
swap Int
5 Int
6
      Int -> Int -> m ()
swap Int
7 Int
8
      Int -> Int -> m ()
swap Int
9 Int
10
      Int -> Int -> m ()
swap Int
11 Int
12
      Int -> Int -> m ()
swap Int
6 Int
7
      Int -> Int -> m ()
swap Int
8 Int
9
    Int
_ ->
      () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
  where
    swap :: Int -> Int -> m ()
    swap :: Int -> Int -> m ()
swap !Int
i !Int
j = do
      !a
x <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
GM.unsafeRead v (PrimState m) a
v Int
i
      !a
y <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
GM.unsafeRead v (PrimState m) a
v Int
j
      Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
        v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
v Int
i a
y
        v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
GM.unsafeWrite v (PrimState m) a
v Int
j a
x