The fastest sorting method for 128 elements?
-
What is the fastest (in average) sorting method for 128 random elements?
Element size is small: 4 or 8 bytes.
I mean not theoretically fastest, but practically fastest. I tested MergeSort, and it is faster than HeapSort, if do not take into account the time of getting and freeing the additional memory buffer. If take into account this time, the HeapSort is faster.
Look at the picture. This is graph of the following value:
http://iproc.ru/wp-content/cache_tex/tex_572a79b6cedf2c6922908855ee3312c8.png
T(n) – sorting time.
n – number of random int32 elements to sorthttp://iproc.ru/materials/ParLection6/sort_time_small2.png
Gray – HeapSort
Blue – MergeSort
Read – CombinedI have 4 mb L3 cache, so HeapSort start to slow down when n > million. Merge sort is not. But all these algorithm are relatively very slow when n<100
P.S.: Please fix pictures in my post...
-
If the elements are integers then Radixsort is the fastest sorting-algorithm I'm aware of.
edit: Didn't you test quicksort?
-
SAn schrieb:
But all these algorithm are relatively very slow when n<100
With only few objects you must also consider the O(n^2) algorithms such als selection sort or insertion sort and for every few objects some nested if elses will probably be the fastest.
-
i dont get it, is your goal 128 elements or an n of more than a million?
for 128 elements your 4mb 2lvl cache does not matter, just the 1lvl cache is what u shall care about.
and use your stack for allocation, 128elemts fit nicely.
for best performance try a branch free implementation.
