most efficient sorting algorithm

[Shadow]

What is the most efficient sorting algorithm for very large arrays ( > 1,000,000 entries). I would expect the largest values to be at the start and end of the list, getting smaller toward the middle, approaching 0 in the middle. I came across one promising one called introsort, but i can't get any information on the actual implementation. Any suggestions?

[bjornredtail]

The wikipedia article talks a bit about how it works. Uh, yeah.
It's kindof and odd sort in that I've never heard of it before. It's new too (1997)... If you are looking at implementations folks have already done, you might look into heapsort, quicksort and mergesort, which all have average case performance of ~O(nlog(n))

[Shadow]

Quicksort is the standard, but the way the data will be structured, I would get almost worst case performance for the first half and almost best case for half the array. Scaling a million entry array like n^2 is too slow. Since I know the structure I might be able to pick pivots a little more carefully though. Hmm.

[bjornredtail]

I have a sinking feeling that I'm now one of the worse computer scientists in the forums :)

Introsort depends on quicksort for it's initial runs, then switches to heapsort. It also chooses one of the middle values for the initial pivit.  http://en.wikipedia.org/wiki/Introsort (yes, I just read from the wiki)

Is it guaranteed to follow that structure? Do you know for sure that the smallest values are going to be in the middle?

[Shadow]

yeah, itll look like nested bowl shapes, with an overall tendency toward 0 in the middle and a maximum value at the ends.

[Shadow]

Quicksort gets through a million entires in ~6 seconds. Heapsort could probably do better, but I don't understand that one yet :P

[Shadow]

and heapsort takes the prize. Man it's annoying to sort 2D arrays, 1D is so much easier...