Binary QuickSort

Legend

The circle shows the actual column in sorting. The actual Key(s) in sorting, is/are green. The sorted columns are dark-green. The red marked rows are in the wrong place and need to be swapped.

Binary Quicksort is an in situ, recursive sorting algorithm. The representation in independent arrays is only to facilitate understanding.

Algorithm

Binary MSD radix sort, also called binary quicksort, can be implemented in-place by splitting the input array into two bins - the 0s bin and the 1s bin. The 0s bin is grown from the beginning of the array, whereas the 1s bin is grown from the end of the array. The 0s bin boundary is placed before the first array element. The 1s bin boundary is placed after the last array element. The most significant bit of the first array element is examined. If this bit is a 1, then the first element is swapped with the element in front of the 1s bin boundary (the last element of the array), and the 1s bin is grown by one element by decrementing the 1s boundary array index. If this bit is a 0, then the first element remains at its current location, and the 0s bin is grown by one element. The next array element examined is the one in front of the 0s bin boundary (i.e. the first element that is not in the 0s bin or the 1s bin). This process continues until the 0s bin and the 1s bin reach each other. The 0s bin and the 1s bin are then sorted recursively based on the next bit of each array element. Recursive processing continues until the least significant bit has been used for sorting. Wikipedia (opens new window)

Pseudocode

do {
    scan top-down to find key starting with 1;
    scan bottom-up to find key starting with 0;
    exchange keys;
} while (not all indices visited)