Does a "binary sort" algorithm exist?

Is there a sorting algorithm that is named "binary sort"? Like merge sort, selection sort, or the other kinds of sorti开发者_如何学编程ng, does a binary sort exist?

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.

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;
    }
}

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

There are some sort's that involve splitting into two peices (merge sort) but I don't beleive that there is a sort called exactly "binary sort".

We do not have a binary sort algorithm, but we do have binary search on a sorted array.

Not sure what your looking for but if your looking for a suitable binary sort algorithm then you want to be aware of your requirements. Each algorithm has its own strengths and weakness.

For example, are you looking for an algorithm that give fastest average performance (e.g. heap search) or fasted worst case (slowest operation) performance (e.g. balanced binary tree). Some are slow if you also need to iterate from one item to the next. If your doing many random operations you are probably more interested in average performance but if you have a need to ensure that any operation is faster than X milliseconds then you may want a different algorithm. Some can be slow if you always adding items at the end of the collection etc.

So have a google for keywords like:

• Red black tree
• heap search
• balanced trees, e.g. http://www.codeproject.com/KB/recipes/redblackcs.aspx?msg=931557

It all comes down to what you need.

There can be a binary sort but the actual array sorted should be in Opposite sense.(i.e., Say you want to sort an array of integers in ascending order...for that, you must have the actual array in descending order.)