##
Package jdsl.core.algo.sorts

Package of sorting algorithms that operate on Sequences (defined in
`jdsl.core.api`).
**See: **

**Description**

**Interface Summary** |

*SortObject* |
Algorithm interface for sorting a sequence according to a given
comparator of elements. |

**Class Summary** |

**ArrayMergeSort** |
Performs a merge-sort in O(n log n) time, provided that the
atRank(int) method of the Sequence works in O(1) time. |

**ArrayQuickSort** |
Performs an in-place quicksort in expected O(n log n)
time, provided that the atRank(int) method of the Sequence operates in
O(1) time. |

**HeapSort** |
Performs a heap-sort in O(n log n) time, provided only that
the replaceElement(.) method of the Sequence works in O(1) time
(and thus the style of implementation of the Sequence is not relevant). |

**ListMergeSort** |
Performs a merge-sort in O(n log n) time, provided that isEmpty(),
first(), insertLast(), and removeFirst() all operate in O(1) time. |

**ListQuickSort** |
Performs an in-place quicksort in expected O(n log n)
time, provided that the first(), last(), after(), and before()
methods of the Sequence work in O(1) time. |

##
Package jdsl.core.algo.sorts Description

Package of sorting algorithms that operate on Sequences (defined in
`jdsl.core.api`). How to order the elements is defined by
implementations of `jdsl.core.api.Comparator`.

Each sorting algorithm class implements the `SortObject`
interface located in this package. Each algorithm modifies directly the
Sequence provided and leaves it in sorted order. The sorts do
not necessarily preserve the Position-element mappings of the
Sequence.

Some algorithm classes are optimized for particular Sequence
implementations. For example, sorting algorithms with the
*Array* prefix expect the `atRank(.)` method of the
provided `Sequence` to operate in constant time, and so run
optimally on array implementations. Algorithms with the
*List* prefix expect that insertions can be done in constant
time, and so run optimally on linked list implementations. However, each
algorithm will correctly sort any `Sequence`.

Running times (time complexities) given for individual algorithms
depend on the assumption that the comparator can compare two
elements in constant time.