JSort

From Wikipedia, the free 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.^[1]

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.