JSort
Encyclopedia
JSort is an in-place sort algorithm that uses build heap twice to largely order the array then finishes with an insertion sort
. JSort is attributed to Jason Morrison.
The first build heap pass converts the array to a heap
, with the least item in the root, which is in the first position of the array. The second build heap pass works in reverse, with the greatest item in root, which is in the last position for this pass. The largely ordered array is finally sorted with insertion sort. Since insertion sort would do all the sorting by itself, the two passes with build heap only save it work, which could be significant.
Build heap partially orders the array very fast, since items may be moved a long way, up to half the length of the array. Items nearer the root are more likely to be in order, since few items were compared with each other. The farther from the root, the more likely items are significantly out of order, since they are not compared with each other, only with their parents. Thus items at the leaves are likely quite unordered, which would cause insertion sort to take a long time.
The second pass reverses the heap and puts the root at the last position in the array. It also reverses the heap sense, so the largest item is at the root. Thus the second pass follows the same general order as the first pass, lesser items near the first position and greater items near the last position, but works more at the last positions. The second pass, then, does most of its work exactly where the first pass did little. Together the two passes mostly order the array. The final insertion sort can run relatively quickly. Complexity is still 0(n^2).
Insertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
. JSort is attributed to Jason Morrison.
The first build heap pass converts the array to a heap
Heap (data structure)
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key ≥ key. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap...
, with the least item in the root, which is in the first position of the array. The second build heap pass works in reverse, with the greatest item in root, which is in the last position for this pass. The largely ordered array is finally sorted with insertion sort. Since insertion sort would do all the sorting by itself, the two passes with build heap only save it work, which could be significant.
Build heap partially orders the array very fast, since items may be moved a long way, up to half the length of the array. Items nearer the root are more likely to be in order, since few items were compared with each other. The farther from the root, the more likely items are significantly out of order, since they are not compared with each other, only with their parents. Thus items at the leaves are likely quite unordered, which would cause insertion sort to take a long time.
The second pass reverses the heap and puts the root at the last position in the array. It also reverses the heap sense, so the largest item is at the root. Thus the second pass follows the same general order as the first pass, lesser items near the first position and greater items near the last position, but works more at the last positions. The second pass, then, does most of its work exactly where the first pass did little. Together the two passes mostly order the array. The final insertion sort can run relatively quickly. Complexity is still 0(n^2).