What's the range of possible values of these integers? If it's a relatively narrow range, a variation of Radix Sort (I call it Shawn Sort) has close to O(n) speed!

Say you're sorting millions of grades, which range from 1-100.

• You make an array of 100 integers, with all elements initialized to 0.

• Iterate over your dataset, incrementing the array element whose index matches the value (grade).

• Traverse the resulting array, outputing the index (as a value) T times, where T is the array element's value.

Sorting a record (database table record, for example), works the same way, but you also store the identities or record numbers in the array, in which each element (which is a tuple) also contains a list of identities / record numbers.

Shawn Sort beats every other sort algorithm decisively, for integers, if the possible values is manageable relative to the size of the dataset.