    {-# LANGUAGE CPP #-}

    -- ---------------------------------------------------------------------------
    -- |
    -- Module      : Data.Vector.Algorithms.Optimal
    -- Copyright   : (c) 2008-2010 Dan Doel
    -- Maintainer  : Dan Doel
    -- Stability   : Experimental
    -- Portability : Portable
    --
    -- Optimal sorts for very small array sizes, or for small numbers of
    -- particular indices in a larger array (to be used, for instance, for
    -- sorting a median of 3 values into the lowest position in an array
    -- for a median-of-3 quicksort).

    -- The code herein was adapted from a C algorithm for optimal sorts
    -- of small arrays. The original code was produced for the article
    -- /Sorting Revisited/ by Paul Hsieh, available here:
    --
    --   http://www.azillionmonkeys.com/qed/sort.html
    --
    -- The LICENSE file contains the relevant copyright information for
    -- the reference C code.

    module Data.Vector.Algorithms.Optimal
           ( sort2ByIndex
           , sort2ByOffset
           , sort3ByIndex
           , sort3ByOffset
           , sort4ByIndex
           , sort4ByOffset
           , Comparison
           ) where

    import Prelude hiding (read, length)

    import Control.Monad.Primitive

    import Data.Vector.Generic.Mutable

    import Data.Vector.Algorithms.Common (Comparison)

    #if MIN_VERSION_vector(0,13,0)
    import qualified Data.Vector.Internal.Check as Ck
    # define CHECK_INDEX(name, i, n) Ck.checkIndex Ck.Unsafe (i) (n)
    #else
    # define CHECK_INDEX(name, i, n) UNSAFE_CHECK(checkIndex) name (i) (n)
    #endif

    #include "vector.h"

    -- | Sorts the elements at the positions 'off' and 'off + 1' in the given
    -- array using the comparison.
    sort2ByOffset :: (PrimMonad m, MVector v e)
                  => Comparison e -> v (PrimState m) e -> Int -> m ()
    sort2ByOffset :: forall (m :: * -> *) (v :: * -> * -> *) e.
    (PrimMonad m, MVector v e) =>
    Comparison e -> v (PrimState m) e -> Int -> m ()
    sort2ByOffset Comparison e
    cmp v (PrimState m) e
    a Int
    off = Comparison e -> v (PrimState m) e -> Int -> Int -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) e.
    (PrimMonad m, MVector v e) =>
    Comparison e -> v (PrimState m) e -> Int -> Int -> m ()
    sort2ByIndex Comparison e
    cmp v (PrimState m) e
    a Int
    off (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1)
    {-# INLINABLE sort2ByOffset #-}

    -- | Sorts the elements at the two given indices using the comparison. This
    -- is essentially a compare-and-swap, although the first index is assumed to
    -- be the 'lower' of the two.
    sort2ByIndex :: (PrimMonad m, MVector v e)
                 => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()
    sort2ByIndex :: forall (m :: * -> *) (v :: * -> * -> *) e.
    (PrimMonad m, MVector v e) =>
    Comparison e -> v (PrimState m) e -> Int -> Int -> m ()
    sort2ByIndex Comparison e
    cmp v (PrimState m) e
    a Int
    i Int
    j = CHECK_INDEX("sort2ByIndex", i, v (PrimState m) e -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    length v (PrimState m) e
    a)
                           (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $ CHECK_INDEX("sort2ByIndex", j, v (PrimState m) e -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    length v (PrimState m) e
    a) (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $  do
      a0 <- v (PrimState m) e -> Int -> m e
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> m a
    unsafeRead v (PrimState m) e
    a Int
    i
      a1 <- unsafeRead a j
      case cmp a0 a1 of
        Ordering
    GT -> v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a1 m () -> m () -> m ()
    forall a b. m a -> m b -> m b
    forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a0
        Ordering
    _  -> () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
    {-# INLINABLE sort2ByIndex #-}

    -- | Sorts the three elements starting at the given offset in the array.
    sort3ByOffset :: (PrimMonad m, MVector v e)
                  => Comparison e -> v (PrimState m) e -> Int -> m ()
    sort3ByOffset :: forall (m :: * -> *) (v :: * -> * -> *) e.
    (PrimMonad m, MVector v e) =>
    Comparison e -> v (PrimState m) e -> Int -> m ()
    sort3ByOffset Comparison e
    cmp v (PrimState m) e
    a Int
    off = Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) e.
    (PrimMonad m, MVector v e) =>
    Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()
    sort3ByIndex Comparison e
    cmp v (PrimState m) e
    a Int
    off (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    2)
    {-# INLINABLE sort3ByOffset #-}

    -- | 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.
    sort3ByIndex :: (PrimMonad m, MVector v e)
                 => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()
    sort3ByIndex :: forall (m :: * -> *) (v :: * -> * -> *) e.
    (PrimMonad m, MVector v e) =>
    Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()
    sort3ByIndex Comparison e
    cmp v (PrimState m) e
    a Int
    i Int
    j Int
    k = CHECK_INDEX("sort3ByIndex", i, v (PrimState m) e -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    length v (PrimState m) e
    a)
                             (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $ CHECK_INDEX("sort3ByIndex", j, v (PrimState m) e -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    length v (PrimState m) e
    a)
                             (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $ CHECK_INDEX("sort3ByIndex", k, v (PrimState m) e -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    length v (PrimState m) e
    a) (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $ do
      a0 <- v (PrimState m) e -> Int -> m e
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> m a
    unsafeRead v (PrimState m) e
    a Int
    i
      a1 <- unsafeRead a j
      a2 <- unsafeRead a k
      case cmp a0 a1 of
        Ordering
    GT -> case Comparison e
    cmp e
    a0 e
    a2 of
                Ordering
    GT -> case Comparison e
    cmp e
    a2 e
    a1 of
                        Ordering
    LT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a2
                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a0
                        Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a1
                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a2
                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a0
                Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a1
                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a0
        Ordering
    _  -> case Comparison e
    cmp e
    a1 e
    a2 of
                Ordering
    GT -> case Comparison e
    cmp e
    a0 e
    a2 of
                        Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a2
                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a0
                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a1
                        Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a2
                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a1
                Ordering
    _  -> () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
    {-# INLINABLE sort3ByIndex #-}

    -- | Sorts the four elements beginning at the offset.
    sort4ByOffset :: (PrimMonad m, MVector v e)
                  => Comparison e -> v (PrimState m) e -> Int -> m ()
    sort4ByOffset :: forall (m :: * -> *) (v :: * -> * -> *) e.
    (PrimMonad m, MVector v e) =>
    Comparison e -> v (PrimState m) e -> Int -> m ()
    sort4ByOffset Comparison e
    cmp v (PrimState m) e
    a Int
    off = Comparison e
    -> v (PrimState m) e -> Int -> Int -> Int -> Int -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) e.
    (PrimMonad m, MVector v e) =>
    Comparison e
    -> v (PrimState m) e -> Int -> Int -> Int -> Int -> m ()
    sort4ByIndex Comparison e
    cmp v (PrimState m) e
    a Int
    off (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    2) (Int
    off Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    3)
    {-# INLINABLE sort4ByOffset #-}

    -- The horror...

    -- | 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.
    sort4ByIndex :: (PrimMonad m, MVector v e)
                 => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> Int -> m ()
    sort4ByIndex :: forall (m :: * -> *) (v :: * -> * -> *) e.
    (PrimMonad m, MVector v e) =>
    Comparison e
    -> v (PrimState m) e -> Int -> Int -> Int -> Int -> m ()
    sort4ByIndex Comparison e
    cmp v (PrimState m) e
    a Int
    i Int
    j Int
    k Int
    l = CHECK_INDEX("sort4ByIndex", i, v (PrimState m) e -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    length v (PrimState m) e
    a)
                               (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $ CHECK_INDEX("sort4ByIndex", j, v (PrimState m) e -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    length v (PrimState m) e
    a)
                               (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $ CHECK_INDEX("sort4ByIndex", k, v (PrimState m) e -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    length v (PrimState m) e
    a)
                               (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $ CHECK_INDEX("sort4ByIndex", l, v (PrimState m) e -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    length v (PrimState m) e
    a) (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $ do
      a0 <- v (PrimState m) e -> Int -> m e
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> m a
    unsafeRead v (PrimState m) e
    a Int
    i
      a1 <- unsafeRead a j
      a2 <- unsafeRead a k
      a3 <- unsafeRead a l
      case cmp a0 a1 of
        Ordering
    GT -> case Comparison e
    cmp e
    a0 e
    a2 of
                Ordering
    GT -> case Comparison e
    cmp e
    a1 e
    a2 of
                        Ordering
    GT -> case Comparison e
    cmp e
    a1 e
    a3 of
                                Ordering
    GT -> case Comparison e
    cmp e
    a2 e
    a3 of
                                        Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a3
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a1
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a0
                                        Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a3
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a1
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a0
                                Ordering
    _  -> case Comparison e
    cmp e
    a0 e
    a3 of
                                        Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a1
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a3
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a0
                                        Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a1
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a0
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a3
                        Ordering
    _ -> case Comparison e
    cmp e
    a2 e
    a3 of
                               Ordering
    GT -> case Comparison e
    cmp e
    a1 e
    a3 of
                                       Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a3
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a1
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a2
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a0
                                       Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a1
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a3
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a2
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a0
                               Ordering
    _  -> case Comparison e
    cmp e
    a0 e
    a3 of
                                       Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a1
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a2
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a3
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a0
                                       Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a1
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a2
                                                v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a0
                                                -- unsafeWrite a l a3
                Ordering
    _  -> case Comparison e
    cmp e
    a0 e
    a3 of
                        Ordering
    GT -> case Comparison e
    cmp e
    a1 e
    a3 of
                                Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a3
                                         -- unsafeWrite a j a1
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a0
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a2
                                Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a1
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a3
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a0
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a2
                        Ordering
    _  -> case Comparison e
    cmp e
    a2 e
    a3 of
                                Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a1
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a0
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a3
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a2
                                Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a1
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a0
                                         -- unsafeWrite a k a2
                                         -- unsafeWrite a l a3
        Ordering
    _  -> case Comparison e
    cmp e
    a1 e
    a2 of
                Ordering
    GT -> case Comparison e
    cmp e
    a0 e
    a2 of
                        Ordering
    GT -> case Comparison e
    cmp e
    a0 e
    a3 of
                                Ordering
    GT -> case Comparison e
    cmp e
    a2 e
    a3 of
                                        Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a3
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a0
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a1
                                        Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a3
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a0
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a1
                                Ordering
    _  -> case Comparison e
    cmp e
    a1 e
    a3 of
                                        Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a0
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a3
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a1
                                        Ordering
    _  -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a0
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a1
                                                 -- unsafeWrite a l a3
                        Ordering
    _  -> case Comparison e
    cmp e
    a2 e
    a3 of
                                Ordering
    GT -> case Comparison e
    cmp e
    a0 e
    a3 of
                                        Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a3
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a0
                                                 -- unsafeWrite a k a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a1
                                        Ordering
    _  -> do -- unsafeWrite a i a0
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a3
                                                 -- unsafeWrite a k a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a1
                                Ordering
    _  -> case Comparison e
    cmp e
    a1 e
    a3 of
                                        Ordering
    GT -> do -- unsafeWrite a i a0
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a3
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a1
                                        Ordering
    _  -> do -- unsafeWrite a i a0
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a2
                                                 v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a1
                                                 -- unsafeWrite a l a3
                Ordering
    _  -> case Comparison e
    cmp e
    a1 e
    a3 of
                        Ordering
    GT -> case Comparison e
    cmp e
    a0 e
    a3 of
                                Ordering
    GT -> do v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    i e
    a3
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a0
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a1
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a2
                                Ordering
    _  -> do -- unsafeWrite a i a0
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    j e
    a3
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a1
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a2
                        Ordering
    _  -> case Comparison e
    cmp e
    a2 e
    a3 of
                                Ordering
    GT -> do -- unsafeWrite a i a0
                                         -- unsafeWrite a j a1
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    k e
    a3
                                         v (PrimState m) e -> Int -> e -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    unsafeWrite v (PrimState m) e
    a Int
    l e
    a2
                                Ordering
    _  -> do -- unsafeWrite a i a0
                                         -- unsafeWrite a j a1
                                         -- unsafeWrite a k a2
                                         -- unsafeWrite a l a3
                                         () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
    {-# INLINABLE sort4ByIndex #-}