Multi-column sorting algorithm
Original Publication Date: 2001-Sep-10
Included in the Prior Art Database: 2003-Jun-19
Problem While sorting rows in a table, a common technique for ordering rows with equal values in the column being sorted is to consider the corresponding values for the rows in other columns until unequal values are found. A common optimization that makes sense from the user's point of view is to consider only the values in columns previously sorted, where the user selects the row to be sorted by clicking on the column header. This invention improves the performance of multiple column sorting by considering the values in the sorted column in the current row order, because the current row order reflects the ordering of values in all previously sorted columns, and by using a sorting implementation that preserves the order of equal values. The advantage of the present invention is that additional string comparisons are never needed to order equal values according to previous sorts. To use the present invention, we generate collation keys for all values in the column (and include in the keys the index of the row for the data). We store the collation keys in an array in the current row order. Then we sort the collation keys using a stable sorting implementation. Finally, because we need the index of the rows in sorted order, we retrieve the indexes from the collation keys.