most efficient sorting algorithm

Started by Shadow, May 01, 2009, 10:22:33 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

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?
<=holbs-.. ..-holbs=> <=holbs-..

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))
0==={=B=J=O=R=N=R=E=D=T=A=I=L==>
AKA, Nevadacow
First person to ever play RWL

"Program testing can be used to show the presence of bugs, but never to show their absence!"-Edsger W. Dijkstra

Visit http://frostnflame.org today!

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.
<=holbs-.. ..-holbs=> <=holbs-..

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?
0==={=B=J=O=R=N=R=E=D=T=A=I=L==>
AKA, Nevadacow
First person to ever play RWL

"Program testing can be used to show the presence of bugs, but never to show their absence!"-Edsger W. Dijkstra

Visit http://frostnflame.org today!

Shadow

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



<=holbs-.. ..-holbs=> <=holbs-..

Shadow

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

Shadow

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