This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug libc/7018] New: bug in _quicksort
- From: "laurent dot deniau at cern dot ch" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: 11 Nov 2008 01:57:29 -0000
- Subject: [Bug libc/7018] New: bug in _quicksort
- Reply-to: sourceware-bugzilla at sourceware dot org
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=7018
------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.