Thread: Sorting issue

Originally Posted by Ssalty

Greetings to all. I am trying to make a quicksort that is faster than the qsort function from the library . So far, I've come to discover that if I choose the pivot at the middle of the sorting vector, my qsort beats the library qsort, but this depends on the size of the vector. At 100k elements, it's ok, but at 1kk elements, from 100 test cases, the library beast my version 100-0.
So the problem is at larger vectors, and in choosing the proper pivot. Can somebody please give me some hints? I would very much appreciate it.

To even contemplate beating a standard library implementation, you probably should be well read enough to know of other pivot selection strategies, e.g., median of three and (pseudo-)random selection. Try them. However, you may find that what constitutes an improvement with larger ranges may result in a slight loss of performance with smaller ranges (e.g., when the range is sufficiently small, you may want to switch to say, insertion sort).

Incidentally, since this is C++, note that we would more typically use std::sort instead of qsort.