[Bug libc/7019] New: bug in _quicksort

[Bug libc/7019] New: bug in _quicksort

[laurent dot deniau at cern dot ch]

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.

-- 
           Summary: bug in _quicksort
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: libc
        AssignedTo: drepper at redhat dot com
        ReportedBy: laurent dot deniau at cern dot ch
                CC: glibc-bugs at sources dot redhat dot com


http://sourceware.org/bugzilla/show_bug.cgi?id=7019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug libc/7019] bug in _quicksort

[laurent dot deniau at cern dot ch]

------- Additional Comments From laurent dot deniau at cern dot ch  2008-11-11 02:03 -------
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 ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |DUPLICATE


http://sourceware.org/bugzilla/show_bug.cgi?id=7019

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.