Does a "binary sort" algorithm exist?

Question

Is there a sorting algorithm that is named "binary sort"? Like merge sort, selection sort, or the other kinds of sorting, does a binary sort exist?

Answer 1

There's this and there's binary insertion sort. The two are pretty similar. They're both quadratic (O(n^2)) time algorithms.

Both algorithms do O(n log n) number of comparisons, but in practice you would also have to move elements around, which would make the entire algorithm quadratic.

Answer 2

The JDK uses a "binary sort" for arrays < size 32 within its Arrays.sort() method. This is actually an insertion sort but using binary search to find the next item instead of linear search.

Here is the code from JDK7

private static void binarySort(Object[] a, int lo, int hi, int start) {
    assert lo <= start && start <= hi;
    if (start == lo)
        start++;
    for ( ; start < hi; start++) {
        @SuppressWarnings("unchecked")
        Comparable<Object> pivot = (Comparable) a[start];

        // Set left (and right) to the index where a[start] (pivot) belongs
        int left = lo;
        int right = start;
        assert left <= right;
        /*
         * Invariants:
         *   pivot >= all in [lo, left).
         *   pivot <  all in [right, start).
         */
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (pivot.compareTo(a[mid]) < 0)
                right = mid;
            else
                left = mid + 1;
        }
        assert left == right;

        /*
         * The invariants still hold: pivot >= all in [lo, left) and
         * pivot < all in [left, start), so pivot belongs at left.  Note
         * that if there are elements equal to pivot, left points to the
         * first slot after them -- that's why this sort is stable.
         * Slide elements over to make room for pivot.
         */
        int n = start - left;  // The number of elements to move
        // Switch is just an optimization for arraycopy in default case
        switch (n) {
            case 2:  a[left + 2] = a[left + 1];
            case 1:  a[left + 1] = a[left];
                     break;
            default: System.arraycopy(a, left, a, left + 1, n);
        }
        a[left] = pivot;
    }
}

Answer 3

A binary sort is a very fast algorithm which involves bit testing. It has a single pass for each bit in the sortable item. For each pass, if the bit is set then the sortable item is stacked at one end of the buffer. If the bit is not set then the item is stacked at the other end of the buffer. Starting the sort at the least significant bit and dealing with the next bits in ascending order will result in the sorted list. I wrote one of these on an early 8086 in 1983 forthe Scottish Education Department. Steve Pitts