Editing Radix sort (section)

===In-place MSD radix sort implementations===
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.<ref>R. Sedgewick, "Algorithms in C++", third edition, 1998, p. 424-427</ref><ref>{{Cite web|url=http://www.drdobbs.com/architecture-and-design/algorithm-improvement-through-performanc/220300654|title=Algorithm Improvement through Performance Measurement: Part 2|first=Victor J.|last=Duvanenko|website=Dr. Dobb's}}</ref> Handling signed [[two's complement]] integers requires treating the most significant bit with the opposite sense, followed by unsigned treatment of the rest of the bits.

In-place MSD binary-radix sort can be extended to larger radix and retain in-place capability. [[Counting sort]] is used to determine the size of each bin and their starting index. Swapping is used to place the current element into its bin, followed by expanding the bin boundary. As the array elements are scanned the bins are skipped over and only elements between bins are processed, until the entire array has been processed and all elements end up in their respective bins. The number of bins is the same as the radix used - e.g. 16 bins for 16-radix. Each pass is based on a single digit (e.g. 4-bits per digit in the case of 16-radix), starting from the [[most significant digit]]. Each bin is then processed recursively using the next digit, until all digits have been used for sorting.<ref>{{Cite web|url=http://www.drdobbs.com/architecture-and-design/algorithm-improvement-through-performanc/221600153|title=Algorithm Improvement through Performance Measurement: Part 3|first=Victor J.|last=Duvanenko|website=Dr. Dobb's}}</ref><ref>{{Cite web|url=http://www.drdobbs.com/parallel/parallel-in-place-radix-sort-simplified/229000734|title=Parallel In-Place Radix Sort Simplified|first=Victor J.|last=Duvanenko|website=Dr. Dobb's}}</ref>

Neither in-place binary-radix sort nor n-bit-radix sort, discussed in paragraphs above, are [[Sorting algorithm#Stability|stable algorithms]].