View Bug Activity | Format For Printing
The _quicksort (stdlib/qsort.c) function is called from the qsort function (merge sort from stdlib/msort.c) when the memory allocation required for merge sort fails, that is typically when the array to sort is huge (uncommon cases). The alternative solution base on in place quicksort should still be highly efficient. This function has a bug in the partitioning algorithm line 151 and 153 where the mid pointer used to point to the pivot is moved to the right_ptr (left_ptr) making the partitions algorithm broken (suboptimal): the left (right) partition (depending on the line) does not anymore guarantee to hold the values lesser (greater) than the pivot. The algorithm still works since the last stage sorting small subfiles is performed by an insertion sort on the full array, hence masking the effect of the bug but increasing the overall complexity. The correct algorithm with three-partitions improvement can be found in "Algorithm in C" from Sedgwick or in the slides "QuickSort is Optimal" also from Sedgwick. I actually use an improved version of this algorithm optimized for 'compare' instead of 'less' and using a pivot as the median-of-three- random values and network sorting for small sizes (<7). The resulting algorithm beats the merge sort of the libc both in speed and number of comparison in almost all cases by about 20-30%. Only almost fully sorted arrays require less comparisons with the merge sort (about 10-15% less) since it converges towards linear complexity O(n) while the quicksort remains in O(n.log n), but the speed of the quicksort remains better unless the compare function has a very high cost. Finally the three-partitioning quicksort gives much better result on array with many duplicated values. An actual implementation of this algorithm can be found in the file http://cos.cvs.sourceforge.net/viewvc/cos/CosStd/src/Array.c?view=markup line 1018 to 1122 (replace geval2(fun,a,b) by cmp(a,b) in the GCMP macro) regards.
seems that I clicked twice on commit, and I don't know how to remove the second copy. sorry. *** This bug has been marked as a duplicate of 7018 ***