CODEWITHSUNDEEP
sorting
GuilleOjeda
GuilleOjeda

Reputation: 3361

Sorting method for not so scrambled data

I want to sort a million numbers. I already have them in memory (let's assume they fit) and I know for a fact it is very very likely that any given number is originally in a position quite close to it's final position after sorting (i.e. the 1000th number in the original data will very very likely end up between positions 900 and 1100 after sorting).

Which sorting method would perform best in this case? And most importantly, why would it perform better than the others? Assuming memory is big enough for any common method.

Upvotes: 0

Views: 42

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

Plain old insertion sort runs in time O(nk) if you run it on n elements that are all at most k spots from their final positions. Many sorting algorithms, notably introsort, use this fact by having the sorting algorithm stop sorting once the elements are close enough and then switching to insertion sort. Since insertion sort has very low constant factors hidden in the big-O, I'd suspect it would work quite well here.

Upvotes: 1

Related Questions