-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Efficient algorithms for vector arrays
--   
--   Efficient algorithms for sorting vector arrays. At some stage other
--   vector algorithms may be added.
@package vector-algorithms
@version 0.8.0.2


-- | 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).
module Data.Vector.Algorithms.Optimal

-- | 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 <tt>lower</tt> of the two.
sort2ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Sorts the elements at the positions <tt>off</tt> and 'off + 1' in the
--   given array using the comparison.
sort2ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Sorts the elements at the three given indices. The indices are assumed
--   to be given from lowest to highest, so if 'l &lt; m &lt; 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 ()

-- | 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 ()

-- | 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 ()

-- | Sorts the four elements beginning at the offset.
sort4ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | A simple insertion sort. Though it's O(n^2), its iterative nature can
--   be beneficial for small arrays. It is used to sort small segments of
--   an array by some of the more heavy-duty, recursive algorithms.
module Data.Vector.Algorithms.Insertion

-- | Sorts an entire array using the default comparison for the type
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()

-- | Sorts an entire array using a given comparison
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()

-- | Sorts the portion of an array delimited by [l,u)
sortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Sorts the portion of the array delimited by [l,u) under the assumption
--   that [l,m) is already sorted.
sortByBounds' :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | This module implements a simple top-down merge sort. The temporary
--   buffer is preallocated to 1/2 the size of the input array, and shared
--   through the entire sorting process to ease the amount of allocation
--   performed in total. This is a stable sort.
module Data.Vector.Algorithms.Merge

-- | Sorts an array using the default comparison.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()

-- | Sorts an array using a custom comparison.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | This module implements American flag sort: an in-place, unstable,
--   bucket sort. Also in contrast to radix sort, the values are inspected
--   in a big endian order, and buckets are sorted via recursive splitting.
--   This, however, makes it sensible for sorting strings in lexicographic
--   order (provided indexing is fast).
--   
--   The algorithm works as follows: at each stage, the array is looped
--   over, counting the number of elements for each bucket. Then, starting
--   at the beginning of the array, elements are permuted in place to
--   reside in the proper bucket, following chains until they reach back to
--   the current base index. Finally, each bucket is sorted recursively.
--   This lends itself well to the aforementioned variable-length strings,
--   and so the algorithm takes a stopping predicate, which is given a
--   representative of the stripe, rather than running for a set number of
--   iterations.
module Data.Vector.Algorithms.AmericanFlag

-- | Sorts an array using the default ordering. Both Lexicographic and Ord
--   are necessary because the algorithm falls back to insertion sort for
--   sufficiently small arrays.
sort :: forall e m v. (PrimMonad m, MVector v e, Lexicographic e, Ord e) => v (PrimState m) e -> m ()

-- | A fully parameterized version of the sorting algorithm. Again, this
--   function takes both radix information and a comparison, because the
--   algorithms falls back to insertion sort for small arrays.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> (e -> Int -> Bool) -> Int -> (Int -> e -> Int) -> v (PrimState m) e -> m ()

-- | Given a representative of a stripe and an index number, this function
--   determines whether to stop sorting.
terminate :: Lexicographic e => e -> Int -> Bool

-- | The methods of this class specify the information necessary to sort
--   arrays using the default ordering. The name <a>Lexicographic</a> is
--   meant to convey that index should return results in a similar way to
--   indexing into a string.
class Lexicographic e

-- | Computes the length of a representative of a stripe. It should take
--   <tt>n</tt> passes to sort values of extent <tt>n</tt>. The extent may
--   not be uniform across all values of the type.
extent :: Lexicographic e => e -> Int

-- | The size of the bucket array necessary for sorting es
size :: Lexicographic e => Proxy e -> Int

-- | Determines which bucket a given element should inhabit for a
--   particular iteration.
index :: Lexicographic e => Int -> e -> Int
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Word.Word8
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Word.Word16
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Word.Word32
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Word.Word64
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Types.Word
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Int.Int8
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Int.Int16
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Int.Int32
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Int.Int64
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic GHC.Types.Int
instance Data.Vector.Algorithms.AmericanFlag.Lexicographic Data.ByteString.Internal.ByteString
instance (Data.Vector.Algorithms.AmericanFlag.Lexicographic a, Data.Vector.Algorithms.AmericanFlag.Lexicographic b) => Data.Vector.Algorithms.AmericanFlag.Lexicographic (a, b)
instance (Data.Vector.Algorithms.AmericanFlag.Lexicographic a, Data.Vector.Algorithms.AmericanFlag.Lexicographic b) => Data.Vector.Algorithms.AmericanFlag.Lexicographic (Data.Either.Either a b)


-- | This module implements operations for working with a quaternary heap
--   stored in an unboxed array. Most heapsorts are defined in terms of a
--   binary heap, in which each internal node has at most two children. By
--   contrast, a quaternary heap has internal nodes with up to four
--   children. This reduces the number of comparisons in a heapsort
--   slightly, and improves locality (again, slightly) by flattening out
--   the heap.
module Data.Vector.Algorithms.Heap

-- | Sorts an entire array using the default ordering.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()

-- | Sorts an entire array using a custom ordering.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()

-- | Sorts a portion of an array [l,u) using a custom ordering
sortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Moves the lowest k elements to the front of the array. The elements
--   will be in no particular order.
select :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()

-- | Moves the lowest (as defined by the comparison) k elements to the
--   front of the array. The elements will be in no particular order.
selectBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Moves the <tt>lowest</tt> k elements in the portion [l,u) of the array
--   into the positions [l,k+l). The elements will be in no particular
--   order.
selectByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Moves the lowest k elements to the front of the array, sorted.
--   
--   The remaining values of the array will be in no particular order.
partialSort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()

-- | Moves the lowest k elements (as defined by the comparison) to the
--   front of the array, sorted.
--   
--   The remaining values of the array will be in no particular order.
partialSortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Moves the lowest k elements in the portion [l,u) of the array into
--   positions [l,k+l), sorted.
--   
--   The remaining values in [l,u) will be in no particular order. Values
--   outside the range [l,u) will be unaffected.
partialSortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Constructs a heap in a portion of an array [l, u), using the values
--   therein.
--   
--   Note: <a>heapify</a> is more efficient than constructing a heap by
--   repeated insertion. Repeated insertion has complexity O(n*log n) while
--   <a>heapify</a> is able to construct a heap in O(n), where n is the
--   number of elements in the heap.
heapify :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Given a heap stored in a portion of an array [l,u), swaps the top of
--   the heap with the element at u and rebuilds the heap.
pop :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Given a heap stored in a portion of an array [l,u) swaps the top of
--   the heap with the element at position t, and rebuilds the heap.
popTo :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Given a heap stored in a portion of an array [l,u), sorts the highest
--   values into [m,u). The elements in [l,m) are not in any particular
--   order.
sortHeap :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Given a heap stored in a portion of an array [l,u) and an element e,
--   inserts the element into the heap, resulting in a heap in [l,u].
--   
--   Note: it is best to only use this operation when incremental
--   construction of a heap is required. <a>heapify</a> is capable of
--   building a heap in O(n) time, while repeated insertion takes O(n*log
--   n) time.
heapInsert :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> e -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | This module implements various algorithms based on the introsort
--   algorithm, originally described by David R. Musser in the paper
--   /Introspective Sorting and Selection Algorithms/. It is also in
--   widespread practical use, as the standard unstable sort used in the
--   C++ Standard Template Library.
--   
--   Introsort is at its core a quicksort. The version implemented here has
--   the following optimizations that make it perform better in practice:
--   
--   <ul>
--   <li>Small segments of the array are left unsorted until a final
--   insertion sort pass. This is faster than recursing all the way down to
--   one-element arrays.</li>
--   <li>The pivot for segment [l,u) is chosen as the median of the
--   elements at l, u-1 and (u+l)/2. This yields good behavior on mostly
--   sorted (or reverse-sorted) arrays.</li>
--   <li>The algorithm tracks its recursion depth, and if it decides it is
--   taking too long (depth greater than 2 * lg n), it switches to a heap
--   sort to maintain O(n lg n) worst case behavior. (This is what makes
--   the algorithm introsort).</li>
--   </ul>
module Data.Vector.Algorithms.Intro

-- | Sorts an entire array using the default ordering.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()

-- | Sorts an entire array using a custom ordering.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()

-- | Sorts a portion of an array [l,u) using a custom ordering
sortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()

-- | Moves the least k elements to the front of the array in no particular
--   order.
select :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()

-- | Moves the least k elements (as defined by the comparison) to the front
--   of the array in no particular order.
selectBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Moves the least k elements in the interval [l,u) to the positions
--   [l,k+l) in no particular order.
selectByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | Moves the least k elements to the front of the array, sorted.
partialSort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()

-- | Moves the least k elements (as defined by the comparison) to the front
--   of the array, sorted.
partialSortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()

-- | Moves the least k elements in the interval [l,u) to the positions
--   [l,k+l), sorted.
partialSortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | This module provides a radix sort for a subclass of unboxed arrays.
--   The radix class gives information on * the number of passes needed for
--   the data type
--   
--   <ul>
--   <li>the size of the auxiliary arrays</li>
--   <li>how to compute the pass-k radix of a value</li>
--   </ul>
--   
--   Radix sort is not a comparison sort, so it is able to achieve O(n) run
--   time, though it also uses O(n) auxiliary space. In addition, there is
--   a constant space overhead of 2*size*sizeOf(Int) for the sort, so it is
--   not advisable to use this sort for large numbers of very small arrays.
--   
--   A standard example (upon which one could base their own Radix
--   instance) is Word32:
--   
--   <ul>
--   <li>We choose to sort on r = 8 bits at a time</li>
--   <li>A Word32 has b = 32 bits total</li>
--   </ul>
--   
--   Thus, b/r = 4 passes are required, 2^r = 256 elements are needed in an
--   auxiliary array, and the radix function is:
--   
--   <pre>
--   radix k e = (e `shiftR` (k*8)) .&amp;. 255
--   </pre>
module Data.Vector.Algorithms.Radix

-- | Sorts an array based on the Radix instance.
sort :: forall e m v. (PrimMonad m, MVector v e, Radix e) => v (PrimState m) e -> m ()

-- | Radix sorts an array using custom radix information requires the
--   number of passes to fully sort the array, the size of of auxiliary
--   arrays necessary (should be one greater than the maximum value
--   returned by the radix function), and a radix function, which takes the
--   pass and an element, and returns the relevant radix.
sortBy :: (PrimMonad m, MVector v e) => Int -> Int -> (Int -> e -> Int) -> v (PrimState m) e -> m ()
class Radix e

-- | The number of passes necessary to sort an array of es
passes :: Radix e => e -> Int

-- | The size of an auxiliary array
size :: Radix e => e -> Int

-- | The radix function parameterized by the current pass
radix :: Radix e => Int -> e -> Int
instance Data.Vector.Algorithms.Radix.Radix GHC.Types.Int
instance Data.Vector.Algorithms.Radix.Radix GHC.Int.Int8
instance Data.Vector.Algorithms.Radix.Radix GHC.Int.Int16
instance Data.Vector.Algorithms.Radix.Radix GHC.Int.Int32
instance Data.Vector.Algorithms.Radix.Radix GHC.Int.Int64
instance Data.Vector.Algorithms.Radix.Radix GHC.Types.Word
instance Data.Vector.Algorithms.Radix.Radix GHC.Word.Word8
instance Data.Vector.Algorithms.Radix.Radix GHC.Word.Word16
instance Data.Vector.Algorithms.Radix.Radix GHC.Word.Word32
instance Data.Vector.Algorithms.Radix.Radix GHC.Word.Word64
instance (Data.Vector.Algorithms.Radix.Radix i, Data.Vector.Algorithms.Radix.Radix j) => Data.Vector.Algorithms.Radix.Radix (i, j)


-- | This module implements several methods of searching for indicies to
--   insert elements into a sorted vector.
module Data.Vector.Algorithms.Search

-- | Finds an index in a given sorted vector at which the given element
--   could be inserted while maintaining the sortedness of the vector.
binarySearch :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m Int

-- | Finds an index in a given vector, which must be sorted with respect to
--   the given comparison function, at which the given element could be
--   inserted while preserving the vector's sortedness.
binarySearchBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int

-- | Given a vector sorted with respect to a given comparison function in
--   indices in [l,u), finds an index in [l,u] at which the given element
--   could be inserted while preserving sortedness.
binarySearchByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int

-- | Finds the lowest index in a given sorted vector at which the given
--   element could be inserted while maintaining the sortedness.
binarySearchL :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m Int

-- | Finds the lowest index in a given vector, which must be sorted with
--   respect to the given comparison function, at which the given element
--   could be inserted while preserving the sortedness.
binarySearchLBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int

-- | Given a vector sorted with respect to a given comparison function on
--   indices in [l,u), finds the lowest index in [l,u] at which the given
--   element could be inserted while preserving sortedness.
binarySearchLByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int

-- | Finds the greatest index in a given sorted vector at which the given
--   element could be inserted while maintaining sortedness.
binarySearchR :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m Int

-- | Finds the greatest index in a given vector, which must be sorted with
--   respect to the given comparison function, at which the given element
--   could be inserted while preserving the sortedness.
binarySearchRBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int

-- | Given a vector sorted with respect to the given comparison function on
--   indices in [l,u), finds the greatest index in [l,u] at which the given
--   element could be inserted while preserving sortedness.
binarySearchRByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int

-- | Given a predicate that is guaraneteed to be monotone on the given
--   vector, finds the first index at which the predicate returns True, or
--   the length of the array if the predicate is false for the entire
--   array.
binarySearchP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int

-- | Given a predicate that is guaranteed to be monotone on the indices
--   [l,u) in a given vector, finds the index in [l,u] at which the
--   predicate turns from False to True (yielding u if the entire interval
--   is False).
binarySearchPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> Int -> Int -> m Int

-- | Given a predicate that is guaranteed to be monotone on the vector
--   elements in order, finds the index at which the predicate turns from
--   False to True. The length of the vector is returned if the predicate
--   is False for the entire vector.
--   
--   Begins searching at the start of the vector, in increasing steps of
--   size 2^n.
gallopingSearchLeftP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int

-- | Given a predicate that is guaranteed to be monotone on the indices
--   [l,u) in a given vector, finds the index in [l,u] at which the
--   predicate turns from False to True (yielding u if the entire interval
--   is False). Begins searching at l, going right in increasing
--   (2^n)-steps.
gallopingSearchLeftPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> Int -> Int -> m Int

-- | Given a predicate that is guaranteed to be monotone on the vector
--   elements in order, finds the index at which the predicate turns from
--   False to True. The length of the vector is returned if the predicate
--   is False for the entire vector.
--   
--   Begins searching at the end of the vector, in increasing steps of size
--   2^n.
gallopingSearchRightP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int

-- | Given a predicate that is guaranteed to be monotone on the indices
--   [l,u) in a given vector, finds the index in [l,u] at which the
--   predicate turns from False to True (yielding u if the entire interval
--   is False). Begins searching at u, going left in increasing
--   (2^n)-steps.
gallopingSearchRightPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> Int -> Int -> m Int

-- | A type of comparisons between two values of a given type.
type Comparison e = e -> e -> Ordering


-- | Timsort is a complex, adaptive, bottom-up merge sort. It is designed
--   to minimize comparisons as much as possible, even at some cost in
--   overhead. Thus, it may not be ideal for sorting simple primitive
--   types, for which comparison is cheap. It may, however, be
--   significantly faster for sorting arrays of complex values (strings
--   would be an example, though an algorithm not based on comparison would
--   probably be superior in that particular case).
--   
--   For more information on the details of the algorithm, read on.
--   
--   The first step of the algorithm is to identify runs of elements. These
--   can either be non-decreasing or strictly decreasing sequences of
--   elements in the input. Strictly decreasing sequences are used rather
--   than non-increasing so that they can be easily reversed in place
--   without the sort becoming unstable.
--   
--   If the natural runs are too short, they are padded to a minimum value.
--   The minimum is chosen based on the length of the array, and padded
--   runs are put in order using insertion sort. The length of the minimum
--   run size is determined as follows:
--   
--   <ul>
--   <li>If the length of the array is less than 64, the minimum size is
--   the length of the array, and insertion sort is used for the
--   entirety</li>
--   <li>Otherwise, a value between 32 and 64 is chosen such that N/min is
--   either equal to or just below a power of two. This avoids having a
--   small chunk left over to merge into much larger chunks at the
--   end.</li>
--   </ul>
--   
--   This is accomplished by taking the the mininum to be the lowest six
--   bits containing the highest set bit, and adding one if any other bits
--   are set. For instance:
--   
--   length: 00000000 00000000 00000000 00011011 = 25 min: 00000000
--   00000000 00000000 00011011 = 25
--   
--   length: 00000000 11111100 00000000 00000000 = 63 * 2^18 min: 00000000
--   00000000 00000000 00111111 = 63
--   
--   length: 00000000 11111100 00000000 00000001 = 63 * 2^18 + 1 min:
--   00000000 00000000 00000000 01000000 = 64
--   
--   Once chunks can be produced, the next step is merging them. The
--   indices of all runs are stored in a stack. When we identify a new run,
--   we push it onto the stack. However, certain invariants are maintained
--   of the stack entries. Namely:
--   
--   if stk = _ :&gt; z :&gt; y :&gt; x length x + length y &lt; length z
--   
--   if stk = _ :&gt; y :&gt; x length x &lt; length y
--   
--   This ensures that the chunks stored are decreasing, and that the chunk
--   sizes follow something like the fibonacci sequence, ensuring there at
--   most log-many chunks at any time. If pushing a new chunk on the stack
--   would violate either of the invariants, we first perform a merge.
--   
--   If length x + length y &gt;= length z, then y is merged with the
--   smaller of x and z (if they are tied, x is chosen, because it is more
--   likely to be cached). If, further, length x &gt;= length y then they
--   are merged. These steps are repeated until the invariants are
--   established.
--   
--   The last important piece of the algorithm is the merging. At first,
--   two chunks are merged element-wise. However, while doing so, counts
--   are kept of the number of elements taken from one chunk without any
--   from its partner. If this count exceeds a threshold, the merge
--   switches to searching for elements from one chunk in the other, and
--   copying chunks at a time. If these chunks start falling below the
--   threshold, the merge switches back to element-wise.
--   
--   The search used in the merge is also special. It uses a galloping
--   strategy, where exponentially increasing indices are tested, and once
--   two such indices are determined to bracket the desired value, binary
--   search is used to find the exact index within that range. This is
--   asymptotically the same as simply using binary search, but is likely
--   to do fewer comparisons than binary search would.
--   
--   One aspect that is not yet implemented from the original Tim sort is
--   the adjustment of the above threshold. When galloping saves time, the
--   threshold is lowered, and when it doesn't, it is raised. This may be
--   implemented in the future.
module Data.Vector.Algorithms.Tim

-- | Sorts an array using the default comparison.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()

-- | Sorts an array using a custom comparison.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()
instance GHC.Show.Show Data.Vector.Algorithms.Tim.Order
instance GHC.Classes.Eq Data.Vector.Algorithms.Tim.Order