no further recursion is needed Next digit: [{ {002}, {025, 024}, {045}, {066}, {075} }, 170, 802] Final digit: [ 002, { {024}, {025} }, 045, 066, 075 , 170, 802] All that remains is concatenation: [002, 024, 025, 045, 066, 075, 170, 802] Complexity and performance Radix sort operates in time, where is the number of keys, and is the key length. LSD variants can achieve a lower bound for of 'average key length' when splitting variable length keys into groups as discussed above. Optimized radix sorts can be very fast when working in a domain that suits them. They are constrained to lexicographic data, but for many practical applications this is not a limitation. Large key sizes can hinder LSD implementations when the induced number of passes becomes the bottleneck. Specialized variants 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. 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