On average qsort is O(N log N) , infact with a 99:1 split mathematically it is still O(N log N) and because it sorts in place it is often the fastest algorithm. Heap sort may be guarenteed O(N log N), but there is a large overhead associated with maintaining the heap and hence it is often slower than qsort with random pivot selection.
I'm using the template and until now I thougt, that it is a great help. But now I found out, that the algorithm not always finds the smalles element in a list, if I sort it in ascending order. It seems to be, that the algorithm sets the second smallest object as the smallest. Does anybody made similar experiences ??
Is it possible to somehow use this sort function with a CArray <MyClass, MyClass> MyClassArray where MyClass contains an int to sort on. Of course MyClass also contains other variables that must remain with the int in MyClass.
Not often you find exactly what you were looking for on the net. your search template method was exactly what i was looking for. i modified it to not modify the passed in array but modify an indexes array instead, but it works perfect!
QuickSort is not the fastest sorting algorithm. QuickSort should also never be used in arrays with more than 256 elements.
The two fastest sorting algorithms, for both large and small arrays, are Heap Sort and Merge Sort. (Heap Sort is guaranteed NlogN order, while QuickSort can become quadratic.)
Finally, QuickSort was one of the first sorting algorithms with much of an advantage over Bubble Sort. However, newer sorting mechanisms have made it practically useless for modern-day sorting (millions or billions of elements).