Patent ID: 9619204
Date: 2017-04-11
CPC Classifications: G06F

Claim:
1. A non-transitory computer readable medium having computer executable instructions for causing a computer system to perform a method for sorting, wherein said method comprises: partitioning a plurality of keys needing sorting into a first plurality of bins that are sequentially sorted, wherein said plurality of keys is capable of being sorted into a sequence of keys using a corresponding ordering system; coalescing a first pair of consecutive bins in isolation from other bins in a first coalescing operation, such that when coalesced said first pair of consecutive bins falls below a threshold; ordering keys in said first pair of consecutive bins that is coalesced to generate a first sub-sequence of keys in said sequence of keys; repeatedly choosing candidate pairs for coalescing by recursive halving of remaining bins in plurality of bins; in parallel using a plurality of processor cores, generating a second plurality of bins by determining when to coalesce each of a plurality of pairs of consecutive bins in said first plurality of bins, such that a pair of consecutive bins when coalesced falls below said threshold; and partitioning, by a top-down, divide-and-conquer sorting algorithm, said plurality of keys into said plurality of bins.