Richard Heathfield wrote:

The best way to make your sort Quick is to use the standard library's

sorting routine.

The truth of that is entirely implementation dependant.

qsort on my implementation,

goes quadratic on worst cases,

and it has more than one kind of worst case,

and it is easy to beat hand coded, for all cases.

Using

http://www.mindspring.com/~pfilandr/C/e_driver/
/* BEGIN e_driver.c program output */

Timing 4 different sorting functions.

Sorting arrays of N number of elements,

in 2 different distributions.

The elements are of type long unsigned.

sizeof (long unsigned) is 4.

The times shown are in seconds.

Distribution #1: Shuffled

N qisort qrsort m_sort qsort

199998 0.110000 0.109000 0.140000 0.156000

199999 0.110000 0.125000 0.140000 0.157000

Total times:

qisort: 0.220000 qsort interface, center pivot introspective

qrsort: 0.234000 qsort interface, random pivot introspective

m_sort: 0.280000 qsort interface, stable merge, TOO_SMALL is 10

qsort: 0.313000 standard library qsort

Distribution #2: Ramp, Drives center pivot qsorts, quadratic

N qisort qrsort m_sort qsort

199998 0.250000 0.094000 0.078000 0.922000

199999 0.266000 0.094000 0.078000 1.250000

Total times:

qisort: 0.516000 qsort interface, center pivot introspective

qrsort: 0.188000 qsort interface, random pivot introspective

m_sort: 0.156000 qsort interface, stable merge, TOO_SMALL is 10

qsort: 2.172000 standard library qsort

/* END e_driver.c program output */

/* BEGIN e_driver.c program output */

Timing 4 different sorting functions.

Sorting arrays of N number of elements.

The elements are of type long unsigned.

sizeof (long unsigned) is 4.

The times shown are in seconds.

Distribution #1: Two values, Badly written qsorts choke on this

N qisort qrsort m_sort qsort

19998 0.000000 0.000000 0.000000 1.594000

19999 0.000000 0.000000 0.000000 1.593000

Total times:

qisort: 0.000000 qsort interface, center pivot introspective

qrsort: 0.000000 qsort interface, random pivot introspective

m_sort: 0.000000 qsort interface, stable merge, TOO_SMALL is 10

qsort: 3.187000 standard library qsort

/* END e_driver.c program output */

--

pete