A system and method for performing sorting. The method includes partitioning a plurality of keys needing sorting into a first plurality of bins, wherein the bins are sequentially sorted. The plurality of keys is capable of being sorted into a sequence of keys using a corresponding ordering system. The method includes coalescing a first pair of consecutive bins, such that when coalesced the first pair of bins falls below a threshold. The method also includes ordering keys in the first coalesced pair to generate a first sub-sequence of keys in the sequence of keys.