Stable duplicate-key extraction with optimal time and space bounds (Q1103387)

We consider the problem of transforming a list L of records sorted on some key into two sublists \(L_ 1\) and \(L_ 2\) where, for each distinct key in L, \(L_ 1\) contains the first record of L that possesses the key and \(L_ 2\) contains all records of L with duplicate keys. We desire that our duplicate-key extraction algorithm performs the transformation in place and is stable (that is, records within each sublist must obey the original order given by L). This operation is useful in database and related file processing environments whenever only distinct keys need be considered. Moreover, stability in extraction insures that L can be efficiently restored at a later time with a stable merge of \(L_ 1\) and \(L_ 2\). Any procedure for performing duplicate-key extraction on a list of size n must require at least O(n) time and O(1) extra space, although the obvious algorithm for achieving either bound alone violates the other bound. We design a stable algorithm, using block-rearrangement techniques, and show that it is optimal in the theoretical sense that it achieves both lower bounds simultaneously. We also prove that its worst-case number of key comparisons and record exchanges sums to no more than 6n, suggesting that the algorithm has practical application as well.