Re: Quicksort
- From: user923005 <dcorbit@xxxxxxxxx>
- Date: Wed, 9 Jan 2008 00:17:09 -0800 (PST)
On Jan 8, 9:32 pm, "cr88192" <cr88...@xxxxxxxxxxx> wrote:
"user923005" <dcor...@xxxxxxxxx> wrote in message
news:52adfe3b-72f1-4d64-acb6-b9813879dc51@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Jan 8, 8:33pm, "cr88192" <cr88...@xxxxxxxxxxx> wrote:
"cr88192" <cr88...@xxxxxxxxxxx> wrote in message
<snip>
Can you send me your working code via email or post your completed,
working version here?
doing a little cleaning and misc:
----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void hsortm(int *array, int nmemb)
{
int p, child, parent;
int temp;
if (nmemb>1)
{
p=(--nmemb)/2;
do {
parent=p;
child=parent * 2;
temp=array[parent];
while ((nmemb-parent)>parent)
{
if (array[child+1]>array[child]) child++;
if (array[child]>temp)
{
array[parent]=array[child];
parent=child;
child*=2;
}else break;
}
if ((nmemb==child) && (array[child]>temp))
{
array[parent]=array[child];
parent=child;
}
array[parent]=temp;
} while (p--);
temp=array[0];
array[0]=array[nmemb];
array[nmemb]=temp;
while (--nmemb)
{
parent=0;
child=parent*2;
temp=array[parent];
while ((nmemb-parent)>parent)
{
if (array[child+1]>array[child]) child++;
if (array[child]>temp)
{
array[parent]=array[child];
parent=child;
child*=2;
} else break;
}
if ((nmemb==child) && (array[child]>temp))
{
array[parent]=array[child];
parent=child;
}
array[parent]=temp;
temp=array[0];
array[0]=array[nmemb];
array[nmemb]=temp;
}
}
}
void Swap(int *arr, int i, int j)
{
int k;
if(i==j)return;
k=arr[i]; arr[i]=arr[j]; arr[j]=k;
}
//#define Swap(arr,i,j) { k=arr[i]; arr[i]=arr[j]; arr[j]=k; }while(0)
void Sort0(int *arr, int base, int lim)
{
static int depth=0;
int mp;
int low, mid, high;
int i, j, k;
if((lim-base)<2)return;
if(depth>=64) //bad case, use selection sort
{
for(i=base; i<lim; i++)
for(j=i+1; j<lim; j++)
if(arr[j]<arr[i])Swap(arr, i, j);
return;
}
depth++;
low=base; high=lim; mid=(low+high)/2;
// mp=arr[mid];
i=arr[low]; j=arr[mid]; k=arr[high-1];
mp=(i<j)?((k<i)?i:j):((i<k)?i:j);
i=low;
while(i<high)
{
if(arr[i]<mp) { Swap(arr, low++, i++); continue; }
if(arr[i]>mp) { Swap(arr, --high, i); continue; }
i++;
}
Sort0(arr, base, low);
Sort0(arr, high, lim);
depth--;
}
void Sort1(int *arr, int base, int lim)
{
static int depth=0;
int mp;
int low, mid, high;
int i, j, k;
if((lim-base)<2)return;
if(depth>=64) //bad case, use selection sort
{
j=1; while(j)
{
j=0; lim--;
for(i=base; i<lim; i++)
if(arr[i+1]<arr[i]) { Swap(arr, i, i+1); j++; }
for(i=lim; i>base; i--)
if(arr[i]<arr[i-1]) { Swap(arr, i, i-1); j++; }
base++;
}
return;
}
depth++;
low=base; high=lim; mid=(low+high)/2;
// mp=arr[mid];
i=arr[low]; j=arr[mid]; k=arr[high-1];
mp=(i<j)?((k<i)?i:j):((i<k)?i:j);
i=low;
while(i<high)
{
if(arr[i]<mp) { Swap(arr, low++, i++); continue; }
if(arr[i]>mp) { Swap(arr, --high, i); continue; }
i++;
}
Sort1(arr, base, low);
Sort1(arr, high, lim);
depth--;
}
void Sort2(int *arr, int base, int lim)
{
static int depth=0;
int mp;
int low, mid, high;
int i, j, k;
if((lim-base)<2)return;
#if 0 //sel-sort leaf-case
if(((lim-base)<10) || (depth>=64))
{
for(i=base; i<lim; i++)
for(j=i+1; j<lim; j++)
if(arr[j]<arr[i])Swap(arr, i, j);
return;
}
#endif
#if 1 //heapsort fallback, aka: crude intro sort
if(depth>=64)
{
hsortm(arr+base, lim-base);
return;
}
#endif
depth++;
low=base; high=lim; mid=(low+high)/2;
// mp=arr[mid];
i=arr[low]; j=arr[mid]; k=arr[high-1];
mp=(i<j)?((k<i)?i:j):((i<k)?i:j);
i=low;
while(i<high)
{
if(arr[i]<mp) { Swap(arr, low++, i++); continue; }
if(arr[i]>mp) { Swap(arr, --high, i); continue; }
i++;
}
Sort2(arr, base, low);
Sort2(arr, high, lim);
depth--;
}
void sortchk(int *arr, int sz)
{
int i, j;
j=sz-1;
for(i=0; i<j; i++)
if(arr[i]>arr[i+1])
{
printf("sort fail\n");
return;
}
}
int main()
{
int *arr;
int i, j, t, sz;
sz=1<<22;
arr=malloc(sz*sizeof(int));
for(i=0; i<sz; i++)arr[i]=rand()*251+rand();
t=clock();
hsortm(arr, sz);
printf("HSort %d\n", clock()-t);
sortchk(arr, sz);
for(i=0; i<sz; i++)arr[i]=rand()*251+rand();
t=clock();
Sort0(arr, 0, sz);
printf("Sort0 %d\n", clock()-t);
sortchk(arr, sz);
for(i=0; i<sz; i++)arr[i]=rand()*251+rand();
t=clock();
Sort1(arr, 0, sz);
printf("Sort1 %d\n", clock()-t);
sortchk(arr, sz);
for(i=0; i<sz; i++)arr[i]=rand()*251+rand();
t=clock();
Sort2(arr, 0, sz);
printf("Sort2 %d\n", clock()-t);
sortchk(arr, sz);
return(0);
}- Hide quoted text -
- Show quoted text -
The function you call Sort2 is called cr88192c in this test.
Sort0 and Sort1 go quadratic and would take too long to complete, so I
removed them from the test.
Sort routine cr88192c works remarkably well on distributions with a
small number of discrete values. I shall have to keep it in my bag of
tricks for that reason, thanks for sharing it.
On the whole, it seems average to above average in comparisons with
other sort routines.
/* BEGIN e_driver.c program output */
Timing 25 different sorting functions.
Sorting arrays of N number of elements,
in 19 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.
Distribution #1: Shuffled
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.422000 1.407000 1.531000 0.266000 1.688000 0.751000
0.797000 1.656000 0.453000 0.438000 0.876000 0.267000 1.282000
0.470000
0.422000 1.625000 0.438000 0.641000 0.267000 1.782000 1.360000
1.360000 1.454000 1.641000 1.766000
2097152 0.391000 1.313000 1.422000 0.250000 2.016000 0.438000
0.798000 1.673000 0.454000 0.454000 0.907000 0.266000 1.203000
0.422000
0.392000 1.516000 0.439000 0.610000 0.282000 2.110000 1.391000
1.469000 1.547000 1.735000 1.531000
Total times:
cr88192c: 0.813000 cocktail sort fallback #2
hsortm: 2.720000 casual heap
hsortx1: 2.953000 heapsort
ti7: 0.516000 ti7qsort, SMALL_PARTITION is 50
hdsort: 3.704000 qsort interface: heapsort siftdown
stable: 1.189000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.595000 Stable iterative merge sort
h_sort: 3.329000 qsort interface, heapsort, down and up
qisort: 0.907000 qsort interface, center pivot introspective
qrsort: 0.892000 qsort interface, random pivot introspective
m_sort: 1.783000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.533000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 2.485000 husort with casual heap
qisort: 0.892000 qsort interface, center pivot introspective
qrsort: 0.814000 qsort interface, random pivot introspective
hesort: 3.141000 hesort, siftdown and siftup
qisort: 0.877000 qsort interface, center pivot introspective
qsort: 1.251000 standard library qsort
tisort: 0.549000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 3.892000 heapsort siftup
HS2: 2.751000 heapSort2 casual heap
husort: 2.829000 James Hu style heapsort
hsort6: 3.001000 heapsort siftup
hsort5: 3.376000 heapsort siftup
HS2p1: 3.297000 heapSort2p1
Distribution #2: card_shuffle, worst case some Shellsorts
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.578000 0.687000 0.453000 0.156000 0.875000 0.203000
0.703000 0.828000 0.297000 0.297000 0.437000 0.140000 0.547000
0.296000
0.296000 0.422000 0.296000 0.453000 0.141000 0.453000 0.453000
0.515000 0.562000 0.422000 0.453000
2097152 0.578000 0.469000 0.421000 0.140000 0.827000 0.171000
0.656000 0.765000 0.249000 0.265000 0.422000 0.125000 0.500000
0.250000
0.656000 0.421000 0.281000 0.468000 0.140000 0.422000 0.672000
0.531000 0.406000 0.453000 0.421000
Total times:
cr88192c: 1.156000 cocktail sort fallback #2
hsortm: 1.156000 casual heap
hsortx1: 0.874000 heapsort
ti7: 0.296000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.702000 qsort interface: heapsort siftdown
stable: 0.374000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.359000 Stable iterative merge sort
h_sort: 1.593000 qsort interface, heapsort, down and up
qisort: 0.546000 qsort interface, center pivot introspective
qrsort: 0.562000 qsort interface, random pivot introspective
m_sort: 0.859000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.265000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 1.047000 husort with casual heap
qisort: 0.546000 qsort interface, center pivot introspective
qrsort: 0.952000 qsort interface, random pivot introspective
hesort: 0.843000 hesort, siftdown and siftup
qisort: 0.577000 qsort interface, center pivot introspective
qsort: 0.921000 standard library qsort
tisort: 0.281000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.875000 heapsort siftup
HS2: 1.125000 heapSort2 casual heap
husort: 1.046000 James Hu style heapsort
hsort6: 0.968000 heapsort siftup
hsort5: 0.875000 heapsort siftup
HS2p1: 0.874000 heapSort2p1
Distribution #3: Reverse sorted
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 1.031000 0.343000 0.328000 0.016000 0.718000 0.234000
0.656000 0.672000 0.125000 0.749000 0.640000 0.062000 0.437000
0.125000
0.265000 0.327000 0.156000 0.234000 0.078000 0.374000 0.359000
0.453000 0.390000 0.344000 0.343000
2097152 1.031000 0.343000 0.343000 0.015000 0.718000 0.234000
0.655000 0.812000 0.140000 0.250000 0.672000 0.063000 0.453000
0.172000
0.234000 0.328000 0.140000 0.499000 0.109000 0.375000 0.359000
0.422000 0.391000 0.343000 0.375000
Total times:
cr88192c: 2.062000 cocktail sort fallback #2
hsortm: 0.686000 casual heap
hsortx1: 0.671000 heapsort
ti7: 0.031000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.436000 qsort interface: heapsort siftdown
stable: 0.468000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.311000 Stable iterative merge sort
h_sort: 1.484000 qsort interface, heapsort, down and up
qisort: 0.265000 qsort interface, center pivot introspective
qrsort: 0.999000 qsort interface, random pivot introspective
m_sort: 1.312000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.125000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.890000 husort with casual heap
qisort: 0.297000 qsort interface, center pivot introspective
qrsort: 0.499000 qsort interface, random pivot introspective
hesort: 0.655000 hesort, siftdown and siftup
qisort: 0.296000 qsort interface, center pivot introspective
qsort: 0.733000 standard library qsort
tisort: 0.187000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.749000 heapsort siftup
HS2: 0.718000 heapSort2 casual heap
husort: 0.875000 James Hu style heapsort
hsort6: 0.781000 heapsort siftup
hsort5: 0.687000 heapsort siftup
HS2p1: 0.718000 heapSort2p1
Distribution #4: Ramp, Drives center pivot qsorts, quadratic
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 1.156000 0.405000 0.374000 0.155000 0.827000 0.202000
0.702000 0.765000 0.875000 0.312000 0.391000 0.468000 0.499000
0.874000
0.312000 0.422000 0.843000 1.313000 0.437000 0.328000 0.375000
0.453000 0.359000 0.328000 0.390000
2097152 1.078000 0.391000 0.375000 0.156000 0.781000 0.156000
0.656000 0.719000 0.796000 0.296000 0.375000 0.453000 0.469000
0.796000
0.296000 0.359000 0.797000 1.250000 0.453000 0.328000 0.375000
0.468000 0.359000 0.328000 0.390000
Total times:
cr88192c: 2.234000 cocktail sort fallback #2
hsortm: 0.796000 casual heap
hsortx1: 0.749000 heapsort
ti7: 0.311000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.608000 qsort interface: heapsort siftdown
stable: 0.358000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.358000 Stable iterative merge sort
h_sort: 1.484000 qsort interface, heapsort, down and up
qisort: 1.671000 qsort interface, center pivot introspective
qrsort: 0.608000 qsort interface, random pivot introspective
m_sort: 0.766000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.921000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.968000 husort with casual heap
qisort: 1.670000 qsort interface, center pivot introspective
qrsort: 0.608000 qsort interface, random pivot introspective
hesort: 0.781000 hesort, siftdown and siftup
qisort: 1.640000 qsort interface, center pivot introspective
qsort: 2.563000 standard library qsort
tisort: 0.890000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.656000 heapsort siftup
HS2: 0.750000 heapSort2 casual heap
husort: 0.921000 James Hu style heapsort
hsort6: 0.718000 heapsort siftup
hsort5: 0.656000 heapsort siftup
HS2p1: 0.780000 heapSort2p1
Distribution #5: Two values, Badly written qsorts choke on this
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.016000 0.202000 0.171000 0.062000 0.406000 0.187000
0.719000 1.094000 0.343000 0.328000 0.438000 0.124000 0.202000
0.343000
0.343000 0.453000 0.343000 0.062000 0.125000 0.484000 0.203000
0.203000 0.469000 0.515000 0.171000
2097152 0.000000 0.172000 0.188000 0.016000 0.391000 0.203000
0.672000 0.860000 0.375000 0.313000 0.454000 0.079000 0.219000
0.313000
0.329000 0.438000 0.329000 0.047000 0.125000 0.469000 0.187000
0.187000 0.484000 0.469000 0.188000
Total times:
cr88192c: 0.016000 cocktail sort fallback #2
hsortm: 0.374000 casual heap
hsortx1: 0.359000 heapsort
ti7: 0.078000 ti7qsort, SMALL_PARTITION is 50
hdsort: 0.797000 qsort interface: heapsort siftdown
stable: 0.390000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.391000 Stable iterative merge sort
h_sort: 1.954000 qsort interface, heapsort, down and up
qisort: 0.718000 qsort interface, center pivot introspective
qrsort: 0.641000 qsort interface, random pivot introspective
m_sort: 0.892000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.203000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.421000 husort with casual heap
qisort: 0.656000 qsort interface, center pivot introspective
qrsort: 0.672000 qsort interface, random pivot introspective
hesort: 0.891000 hesort, siftdown and siftup
qisort: 0.672000 qsort interface, center pivot introspective
qsort: 0.109000 standard library qsort
tisort: 0.250000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.953000 heapsort siftup
HS2: 0.390000 heapSort2 casual heap
husort: 0.390000 James Hu style heapsort
hsort6: 0.953000 heapsort siftup
hsort5: 0.984000 heapsort siftup
HS2p1: 0.359000 heapSort2p1
Distribution #6: Already sorted
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 1.188000 0.359000 0.328000 0.000000 0.781000 0.062000
0.687000 0.750000 0.109000 0.187000 0.109000 0.047000 0.421000
0.093000
0.219000 0.296000 0.109000 0.250000 0.062000 0.280000 0.359000
0.437000 0.312000 0.281000 0.343000
2097152 1.203000 0.359000 0.328000 -0.001000 0.796000 0.063000
0.687000 0.719000 0.109000 0.218000 0.093000 0.078000 0.422000
0.109000
0.203000 0.297000 0.109000 0.266000 0.094000 0.296000 0.359000
0.421000 0.296000 0.281000 0.344000
Total times:
cr88192c: 2.391000 cocktail sort fallback #2
hsortm: 0.718000 casual heap
hsortx1: 0.656000 heapsort
ti7: -0.001000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.577000 qsort interface: heapsort siftdown
stable: 0.125000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.374000 Stable iterative merge sort
h_sort: 1.469000 qsort interface, heapsort, down and up
qisort: 0.218000 qsort interface, center pivot introspective
qrsort: 0.405000 qsort interface, random pivot introspective
m_sort: 0.202000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.125000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.843000 husort with casual heap
qisort: 0.202000 qsort interface, center pivot introspective
qrsort: 0.422000 qsort interface, random pivot introspective
hesort: 0.593000 hesort, siftdown and siftup
qisort: 0.218000 qsort interface, center pivot introspective
qsort: 0.516000 standard library qsort
tisort: 0.156000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.576000 heapsort siftup
HS2: 0.718000 heapSort2 casual heap
husort: 0.858000 James Hu style heapsort
hsort6: 0.608000 heapsort siftup
hsort5: 0.562000 heapsort siftup
HS2p1: 0.687000 heapSort2p1
Distribution #7: Constant
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.016000 0.015000 0.016000 0.000000 0.031000 0.062000
0.688000 0.968000 0.313000 0.297000 0.124000 0.094000 0.015000
0.312000
0.312000 0.672000 0.313000 0.015000 0.109000 0.719000 0.015000
0.030000 0.749000 0.765000 0.016000
2097152 0.032000 0.016000 0.017000 0.001000 0.047000 0.094000
0.688000 0.938000 0.329000 0.329000 0.110000 0.095000 0.063000
0.298000
0.298000 0.657000 0.345000 0.016000 0.126000 0.751000 0.016000
0.016000 0.750000 0.766000 0.016000
Total times:
cr88192c: 0.048000 cocktail sort fallback #2
hsortm: 0.031000 casual heap
hsortx1: 0.033000 heapsort
ti7: 0.001000 ti7qsort, SMALL_PARTITION is 50
hdsort: 0.078000 qsort interface: heapsort siftdown
stable: 0.156000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.376000 Stable iterative merge sort
h_sort: 1.906000 qsort interface, heapsort, down and up
qisort: 0.642000 qsort interface, center pivot introspective
qrsort: 0.626000 qsort interface, random pivot introspective
m_sort: 0.234000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.189000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.078000 husort with casual heap
qisort: 0.610000 qsort interface, center pivot introspective
qrsort: 0.610000 qsort interface, random pivot introspective
hesort: 1.329000 hesort, siftdown and siftup
qisort: 0.658000 qsort interface, center pivot introspective
qsort: 0.031000 standard library qsort
tisort: 0.235000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 1.470000 heapsort siftup
HS2: 0.031000 heapSort2 casual heap
husort: 0.046000 James Hu style heapsort
hsort6: 1.499000 heapsort siftup
hsort5: 1.531000 heapsort siftup
HS2p1: 0.032000 heapSort2p1
Distribution #8: Reverse sorted
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 1.110000 0.360000 0.360000 0.032000 0.766000 0.235000
0.672000 0.719000 0.126000 0.282000 0.626000 0.063000 0.439000
0.125000
0.282000 0.329000 0.125000 0.235000 0.110000 0.376000 0.360000
0.438000 0.391000 0.376000 0.360000
2097152 1.093000 0.375000 0.359000 0.015000 0.797000 0.281000
0.749000 0.718000 0.140000 0.234000 0.671000 0.062000 0.563000
0.124000
0.249000 0.327000 0.140000 0.313000 0.078000 0.375000 0.359000
0.421000 0.375000 0.359000 0.375000
Total times:
cr88192c: 2.203000 cocktail sort fallback #2
hsortm: 0.735000 casual heap
hsortx1: 0.719000 heapsort
ti7: 0.047000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.563000 qsort interface: heapsort siftdown
stable: 0.516000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.421000 Stable iterative merge sort
h_sort: 1.437000 qsort interface, heapsort, down and up
qisort: 0.266000 qsort interface, center pivot introspective
qrsort: 0.516000 qsort interface, random pivot introspective
m_sort: 1.297000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.125000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 1.002000 husort with casual heap
qisort: 0.249000 qsort interface, center pivot introspective
qrsort: 0.531000 qsort interface, random pivot introspective
hesort: 0.656000 hesort, siftdown and siftup
qisort: 0.265000 qsort interface, center pivot introspective
qsort: 0.548000 standard library qsort
tisort: 0.188000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.751000 heapsort siftup
HS2: 0.719000 heapSort2 casual heap
husort: 0.859000 James Hu style heapsort
hsort6: 0.766000 heapsort siftup
hsort5: 0.735000 heapsort siftup
HS2p1: 0.735000 heapSort2p1
Distribution #9: Ramp, Drives center pivot qsorts, quadratic
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 1.156000 0.406000 0.390000 0.172000 0.828000 0.156000
0.703000 0.781000 0.844000 0.312000 0.391000 0.468000 0.515000
0.859000
0.297000 0.375000 0.843000 1.405000 0.469000 0.359000 0.406000
0.531000 0.375000 0.343000 0.375000
2097152 1.468000 0.453000 0.421000 0.140000 0.828000 0.188000
0.703000 0.812000 0.828000 0.297000 0.375000 0.453000 0.468000
0.813000
0.297000 0.344000 0.796000 1.249000 0.827000 0.327000 0.390000
0.453000 0.343000 0.328000 0.375000
Total times:
cr88192c: 2.624000 cocktail sort fallback #2
hsortm: 0.859000 casual heap
hsortx1: 0.811000 heapsort
ti7: 0.312000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.656000 qsort interface: heapsort siftdown
stable: 0.344000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.406000 Stable iterative merge sort
h_sort: 1.593000 qsort interface, heapsort, down and up
qisort: 1.672000 qsort interface, center pivot introspective
qrsort: 0.609000 qsort interface, random pivot introspective
m_sort: 0.766000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.921000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.983000 husort with casual heap
qisort: 1.672000 qsort interface, center pivot introspective
qrsort: 0.594000 qsort interface, random pivot introspective
hesort: 0.719000 hesort, siftdown and siftup
qisort: 1.639000 qsort interface, center pivot introspective
qsort: 2.654000 standard library qsort
tisort: 1.296000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.686000 heapsort siftup
HS2: 0.796000 heapSort2 casual heap
husort: 0.984000 James Hu style heapsort
hsort6: 0.718000 heapsort siftup
hsort5: 0.671000 heapsort siftup
HS2p1: 0.750000 heapSort2p1
Distribution #10: Two values, Badly written qsorts choke on this
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.031000 0.249000 0.171000 0.031000 0.406000 0.203000
0.734000 0.843000 0.344000 0.328000 0.453000 0.093000 0.218000
0.343000
0.344000 0.453000 0.343000 0.031000 0.109000 0.484000 0.172000
0.234000 0.484000 0.484000 0.171000
2097152 0.031000 0.172000 0.187000 0.031000 0.405000 0.218000
0.750000 0.844000 0.343000 0.344000 0.469000 0.093000 0.203000
0.344000
0.328000 0.453000 0.344000 0.328000 0.109000 0.484000 0.203000
0.203000 0.516000 0.531000 0.172000
Total times:
cr88192c: 0.062000 cocktail sort fallback #2
hsortm: 0.421000 casual heap
hsortx1: 0.358000 heapsort
ti7: 0.062000 ti7qsort, SMALL_PARTITION is 50
hdsort: 0.811000 qsort interface: heapsort siftdown
stable: 0.421000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.484000 Stable iterative merge sort
h_sort: 1.687000 qsort interface, heapsort, down and up
qisort: 0.687000 qsort interface, center pivot introspective
qrsort: 0.672000 qsort interface, random pivot introspective
m_sort: 0.922000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.186000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.421000 husort with casual heap
qisort: 0.687000 qsort interface, center pivot introspective
qrsort: 0.672000 qsort interface, random pivot introspective
hesort: 0.906000 hesort, siftdown and siftup
qisort: 0.687000 qsort interface, center pivot introspective
qsort: 0.359000 standard library qsort
tisort: 0.218000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.968000 heapsort siftup
HS2: 0.375000 heapSort2 casual heap
husort: 0.437000 James Hu style heapsort
hsort6: 1.000000 heapsort siftup
hsort5: 1.015000 heapsort siftup
HS2p1: 0.343000 heapSort2p1
Distribution #11: Already sorted
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 1.234000 0.359000 0.328000 0.000000 0.781000 0.093000
0.719000 0.766000 0.109000 0.203000 0.109000 0.046000 0.438000
0.124000
0.187000 0.313000 0.109000 0.234000 0.062000 0.265000 0.344000
0.453000 0.281000 0.281000 0.344000
2097152 1.437000 0.359000 0.344000 0.000000 0.796000 0.062000
0.703000 1.015000 0.140000 0.188000 0.124000 0.046000 0.438000
0.124000
0.187000 0.312000 0.140000 0.219000 0.093000 0.249000 0.359000
0.437000 0.312000 0.250000 0.327000
Total times:
cr88192c: 2.671000 cocktail sort fallback #2
hsortm: 0.718000 casual heap
hsortx1: 0.672000 heapsort
ti7: 0.000000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.577000 qsort interface: heapsort siftdown
stable: 0.155000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.422000 Stable iterative merge sort
h_sort: 1.781000 qsort interface, heapsort, down and up
qisort: 0.249000 qsort interface, center pivot introspective
qrsort: 0.391000 qsort interface, random pivot introspective
m_sort: 0.233000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.092000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.876000 husort with casual heap
qisort: 0.248000 qsort interface, center pivot introspective
qrsort: 0.374000 qsort interface, random pivot introspective
hesort: 0.625000 hesort, siftdown and siftup
qisort: 0.249000 qsort interface, center pivot introspective
qsort: 0.453000 standard library qsort
tisort: 0.155000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.514000 heapsort siftup
HS2: 0.703000 heapSort2 casual heap
husort: 0.890000 James Hu style heapsort
hsort6: 0.593000 heapsort siftup
hsort5: 0.531000 heapsort siftup
HS2p1: 0.671000 heapSort2p1
Distribution #12: Constant
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.031000 0.016000 0.031000 0.000000 0.046000 0.077000
0.734000 0.984000 0.312000 0.328000 0.109000 0.093000 0.031000
0.312000
0.297000 0.625000 0.328000 0.031000 0.125000 0.765000 0.015000
0.016000 0.765000 0.749000 0.031000
2097152 0.000000 0.015000 0.016000 -0.001000 0.062000 0.062000
0.719000 0.938000 0.297000 0.344000 0.125000 0.093000 0.015000
0.312000
0.359000 0.656000 0.297000 0.047000 0.094000 0.765000 0.015000
0.015000 0.734000 0.734000 0.031000
Total times:
cr88192c: 0.031000 cocktail sort fallback #2
hsortm: 0.031000 casual heap
hsortx1: 0.047000 heapsort
ti7: -0.001000 ti7qsort, SMALL_PARTITION is 50
hdsort: 0.108000 qsort interface: heapsort siftdown
stable: 0.139000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.453000 Stable iterative merge sort
h_sort: 1.922000 qsort interface, heapsort, down and up
qisort: 0.609000 qsort interface, center pivot introspective
qrsort: 0.672000 qsort interface, random pivot introspective
m_sort: 0.234000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.186000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.046000 husort with casual heap
qisort: 0.624000 qsort interface, center pivot introspective
qrsort: 0.656000 qsort interface, random pivot introspective
hesort: 1.281000 hesort, siftdown and siftup
qisort: 0.625000 qsort interface, center pivot introspective
qsort: 0.078000 standard library qsort
tisort: 0.219000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 1.530000 heapsort siftup
HS2: 0.030000 heapSort2 casual heap
husort: 0.031000 James Hu style heapsort
hsort6: 1.499000 heapsort siftup
hsort5: 1.483000 heapsort siftup
HS2p1: 0.062000 heapSort2p1
Distribution #13: 32 bit RAND
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.406000 1.422000 1.546000 0.266000 1.718000 0.437000
0.797000 1.656000 0.437000 0.405000 0.906000 0.249000 1.281000
0.437000
0.499000 1.625000 0.438000 0.640000 0.266000 1.749000 1.422000
1.437000 1.453000 1.640000 1.437000
2097152 0.391000 1.577000 1.468000 0.250000 1.609000 0.421000
0.750000 1.844000 0.515000 0.422000 0.921000 0.281000 1.359000
0.422000
0.453000 1.625000 0.437000 0.655000 0.281000 1.827000 1.359000
1.328000 1.468000 2.078000 1.531000
Total times:
cr88192c: 0.797000 cocktail sort fallback #2
hsortm: 2.999000 casual heap
hsortx1: 3.014000 heapsort
ti7: 0.516000 ti7qsort, SMALL_PARTITION is 50
hdsort: 3.327000 qsort interface: heapsort siftdown
stable: 0.858000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.547000 Stable iterative merge sort
h_sort: 3.500000 qsort interface, heapsort, down and up
qisort: 0.952000 qsort interface, center pivot introspective
qrsort: 0.827000 qsort interface, random pivot introspective
m_sort: 1.827000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.530000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 2.640000 husort with casual heap
qisort: 0.859000 qsort interface, center pivot introspective
qrsort: 0.952000 qsort interface, random pivot introspective
hesort: 3.250000 hesort, siftdown and siftup
qisort: 0.875000 qsort interface, center pivot introspective
qsort: 1.295000 standard library qsort
tisort: 0.547000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 3.576000 heapsort siftup
HS2: 2.781000 heapSort2 casual heap
husort: 2.765000 James Hu style heapsort
hsort6: 2.921000 heapsort siftup
hsort5: 3.718000 heapsort siftup
HS2p1: 2.968000 heapSort2p1
Distribution #14: Five values
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.047000 0.298000 0.297000 0.063000 0.689000 0.298000
0.751000 0.797000 0.376000 0.360000 0.610000 0.126000 0.360000
0.360000
0.345000 0.360000 0.345000 0.110000 0.126000 0.360000 0.297000
0.345000 0.391000 0.360000 0.298000
2097152 0.077000 0.280000 0.281000 0.078000 0.656000 0.328000
0.734000 0.797000 0.359000 0.359000 0.655000 0.109000 0.374000
0.327000
0.343000 0.327000 0.343000 0.093000 0.109000 0.328000 0.281000
0.343000 0.344000 0.343000 0.266000
Total times:
cr88192c: 0.124000 cocktail sort fallback #2
hsortm: 0.578000 casual heap
hsortx1: 0.578000 heapsort
ti7: 0.141000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.345000 qsort interface: heapsort siftdown
stable: 0.626000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.485000 Stable iterative merge sort
h_sort: 1.594000 qsort interface, heapsort, down and up
qisort: 0.735000 qsort interface, center pivot introspective
qrsort: 0.719000 qsort interface, random pivot introspective
m_sort: 1.265000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.235000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.734000 husort with casual heap
qisort: 0.687000 qsort interface, center pivot introspective
qrsort: 0.688000 qsort interface, random pivot introspective
hesort: 0.687000 hesort, siftdown and siftup
qisort: 0.688000 qsort interface, center pivot introspective
qsort: 0.203000 standard library qsort
tisort: 0.235000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.688000 heapsort siftup
HS2: 0.578000 heapSort2 casual heap
husort: 0.688000 James Hu style heapsort
hsort6: 0.735000 heapsort siftup
hsort5: 0.703000 heapsort siftup
HS2p1: 0.564000 heapSort2p1
Distribution #15: Ten values
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 -0.016000 0.266000 0.281000 0.047000 0.703000 0.266000
0.657000 0.750000 0.312000 0.297000 0.609000 0.047000 0.360000
0.313000
0.313000 0.297000 0.313000 0.078000 0.063000 0.281000 0.375000
0.344000 0.297000 0.281000 0.265000
2097152 0.046000 0.359000 0.344000 0.078000 0.796000 0.359000
0.750000 0.859000 0.375000 0.359000 0.734000 0.124000 0.453000
0.359000
0.359000 0.359000 0.375000 0.141000 0.125000 0.359000 0.437000
0.406000 0.344000 0.328000 0.328000
Total times:
cr88192c: 0.030000 cocktail sort fallback #2
hsortm: 0.625000 casual heap
hsortx1: 0.625000 heapsort
ti7: 0.125000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.499000 qsort interface: heapsort siftdown
stable: 0.625000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.407000 Stable iterative merge sort
h_sort: 1.609000 qsort interface, heapsort, down and up
qisort: 0.687000 qsort interface, center pivot introspective
qrsort: 0.656000 qsort interface, random pivot introspective
m_sort: 1.343000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.171000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.813000 husort with casual heap
qisort: 0.672000 qsort interface, center pivot introspective
qrsort: 0.672000 qsort interface, random pivot introspective
hesort: 0.656000 hesort, siftdown and siftup
qisort: 0.688000 qsort interface, center pivot introspective
qsort: 0.219000 standard library qsort
tisort: 0.188000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.640000 heapsort siftup
HS2: 0.812000 heapSort2 casual heap
husort: 0.750000 James Hu style heapsort
hsort6: 0.641000 heapsort siftup
hsort5: 0.609000 heapsort siftup
HS2p1: 0.593000 heapSort2p1
Distribution #16: Twenty values
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.063000 0.469000 0.672000 0.078000 0.859000 0.343000
0.749000 0.843000 0.375000 0.375000 0.765000 0.125000 0.499000
0.375000
0.374000 0.406000 0.390000 0.156000 0.124000 0.391000 0.437000
0.703000 0.437000 0.406000 0.421000
2097152 0.094000 0.421000 0.390000 0.203000 0.890000 0.344000
0.765000 0.859000 0.375000 0.359000 0.750000 0.140000 0.499000
0.374000
0.375000 0.391000 0.374000 0.156000 0.124000 0.374000 0.406000
0.437000 0.422000 0.374000 0.406000
Total times:
cr88192c: 0.157000 cocktail sort fallback #2
hsortm: 0.890000 casual heap
hsortx1: 1.062000 heapsort
ti7: 0.281000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.749000 qsort interface: heapsort siftdown
stable: 0.687000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.514000 Stable iterative merge sort
h_sort: 1.702000 qsort interface, heapsort, down and up
qisort: 0.750000 qsort interface, center pivot introspective
qrsort: 0.734000 qsort interface, random pivot introspective
m_sort: 1.515000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.265000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.998000 husort with casual heap
qisort: 0.749000 qsort interface, center pivot introspective
qrsort: 0.749000 qsort interface, random pivot introspective
hesort: 0.797000 hesort, siftdown and siftup
qisort: 0.764000 qsort interface, center pivot introspective
qsort: 0.312000 standard library qsort
tisort: 0.248000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.765000 heapsort siftup
HS2: 0.843000 heapSort2 casual heap
husort: 1.140000 James Hu style heapsort
hsort6: 0.859000 heapsort siftup
hsort5: 0.780000 heapsort siftup
HS2p1: 0.827000 heapSort2p1
Distribution #17: 0x7fff values
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.234000 1.405000 1.547000 0.203000 1.796000 0.421000
0.797000 1.859000 0.422000 0.422000 0.859000 0.203000 1.296000
0.452000
0.405000 1.609000 0.421000 0.484000 0.218000 1.828000 1.375000
1.406000 1.468000 1.609000 1.421000
2097152 0.234000 1.734000 1.437000 0.219000 1.656000 0.406000
0.734000 1.921000 0.452000 0.421000 0.874000 0.249000 1.296000
0.421000
0.422000 1.641000 0.421000 0.484000 0.234000 1.719000 1.406000
1.328000 1.453000 1.625000 1.906000
Total times:
cr88192c: 0.468000 cocktail sort fallback #2
hsortm: 3.139000 casual heap
hsortx1: 2.984000 heapsort
ti7: 0.422000 ti7qsort, SMALL_PARTITION is 50
hdsort: 3.452000 qsort interface: heapsort siftdown
stable: 0.827000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.531000 Stable iterative merge sort
h_sort: 3.780000 qsort interface, heapsort, down and up
qisort: 0.874000 qsort interface, center pivot introspective
qrsort: 0.843000 qsort interface, random pivot introspective
m_sort: 1.733000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.452000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 2.592000 husort with casual heap
qisort: 0.873000 qsort interface, center pivot introspective
qrsort: 0.827000 qsort interface, random pivot introspective
hesort: 3.250000 hesort, siftdown and siftup
qisort: 0.842000 qsort interface, center pivot introspective
qsort: 0.968000 standard library qsort
tisort: 0.452000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 3.547000 heapsort siftup
HS2: 2.781000 heapSort2 casual heap
husort: 2.734000 James Hu style heapsort
hsort6: 2.921000 heapsort siftup
hsort5: 3.234000 heapsort siftup
HS2p1: 3.327000 heapSort2p1
Distribution #18: Camel, for floating types
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.016000 0.204000 0.189000 0.063000 0.438000 0.188000
0.719000 0.844000 0.328000 0.344000 0.453000 0.110000 0.204000
0.329000
0.329000 0.454000 0.329000 0.032000 0.125000 0.469000 0.188000
0.219000 0.485000 0.501000 0.188000
2097152 0.030000 0.172000 0.203000 0.047000 0.438000 0.171000
0.718000 0.859000 0.296000 0.312000 0.515000 0.094000 0.234000
0.343000
0.297000 0.453000 0.328000 0.031000 0.109000 0.484000 0.203000
0.234000 0.484000 0.469000 0.187000
Total times:
cr88192c: 0.046000 cocktail sort fallback #2
hsortm: 0.376000 casual heap
hsortx1: 0.392000 heapsort
ti7: 0.110000 ti7qsort, SMALL_PARTITION is 50
hdsort: 0.876000 qsort interface: heapsort siftdown
stable: 0.359000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.437000 Stable iterative merge sort
h_sort: 1.703000 qsort interface, heapsort, down and up
qisort: 0.624000 qsort interface, center pivot introspective
qrsort: 0.656000 qsort interface, random pivot introspective
m_sort: 0.968000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.204000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 0.438000 husort with casual heap
qisort: 0.672000 qsort interface, center pivot introspective
qrsort: 0.626000 qsort interface, random pivot introspective
hesort: 0.907000 hesort, siftdown and siftup
qisort: 0.657000 qsort interface, center pivot introspective
qsort: 0.063000 standard library qsort
tisort: 0.234000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 0.953000 heapsort siftup
HS2: 0.391000 heapSort2 casual heap
husort: 0.453000 James Hu style heapsort
hsort6: 0.969000 heapsort siftup
hsort5: 0.970000 heapsort siftup
HS2p1: 0.375000 heapSort2p1
Distribution #19: Perverse
N cr88192c hsortm hsortx1 ti7 hdsort
stable imsort h_sort qisort qrsort m_sort itsort
husort2 qisort
qrsort hesort qisort qsort tisort hsort5
HS2 husort hsort6 hsort5 HS2p1
2097151 0.078000 0.609000 0.656000 0.063000 0.922000 0.282000
0.720000 1.094000 0.344000 0.313000 0.673000 0.094000 0.610000
0.360000
0.329000 0.766000 0.344000 0.172000 0.125000 0.829000 0.579000
0.673000 0.829000 0.797000 0.719000
2097152 0.157000 0.626000 0.704000 0.110000 0.969000 0.313000
0.766000 1.125000 0.392000 0.344000 0.672000 0.142000 0.610000
0.360000
0.344000 0.782000 0.376000 0.204000 0.157000 0.814000 0.610000
0.845000 0.798000 0.813000 0.641000
Total times:
cr88192c: 0.235000 cocktail sort fallback #2
hsortm: 1.235000 casual heap
hsortx1: 1.360000 heapsort
ti7: 0.173000 ti7qsort, SMALL_PARTITION is 50
hdsort: 1.891000 qsort interface: heapsort siftdown
stable: 0.595000 Stable merge sort: SMALL_MERGE is 1
imsort: 1.486000 Stable iterative merge sort
h_sort: 2.219000 qsort interface, heapsort, down and up
qisort: 0.736000 qsort interface, center pivot introspective
qrsort: 0.657000 qsort interface, random pivot introspective
m_sort: 1.345000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 0.236000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 1.220000 husort with casual heap
qisort: 0.720000 qsort interface, center pivot introspective
qrsort: 0.673000 qsort interface, random pivot introspective
hesort: 1.548000 hesort, siftdown and siftup
qisort: 0.720000 qsort interface, center pivot introspective
qsort: 0.376000 standard library qsort
tisort: 0.282000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 1.643000 heapsort siftup
HS2: 1.189000 heapSort2 casual heap
husort: 1.518000 James Hu style heapsort
hsort6: 1.627000 heapsort siftup
hsort5: 1.610000 heapsort siftup
HS2p1: 1.360000 heapSort2p1
GRAND Total times:
cr88192c: 18.168000 cocktail sort fallback #2
hsortm: 19.087000 casual heap
hsortx1: 18.917000 heapsort
ti7: 3.420000 ti7qsort, SMALL_PARTITION is 50
hdsort: 30.756000 qsort interface: heapsort siftdown
stable: 9.212000 Stable merge sort: SMALL_MERGE is 1
imsort: 27.357000 Stable iterative merge sort
h_sort: 37.746000 qsort interface, heapsort, down and up
qisort: 13.808000 qsort interface, center pivot introspective
qrsort: 12.685000 qsort interface, random pivot introspective
m_sort: 19.496000 qsort interface, stable merge, TOO_SMALL is 10
itsort: 5.964000 Introquicksort with insertionsort,
SMALL_PARTITION is 50
husort2: 19.495000 husort with casual heap
qisort: 13.585000 qsort interface, center pivot introspective
qrsort: 12.591000 qsort interface, random pivot introspective
hesort: 23.515000 hesort, siftdown and siftup
qisort: 13.637000 qsort interface, center pivot introspective
qsort: 13.652000 standard library qsort
tisort: 6.810000 Introquicksort with ifelse for partitions
smaller than 5
hsort5: 25.432000 heapsort siftup
HS2: 18.481000 heapSort2 casual heap
husort: 20.214000 James Hu style heapsort
hsort6: 23.777000 heapsort siftup
hsort5: 24.730000 heapsort siftup
HS2p1: 19.322000 heapSort2p1
/* END e_driver.c program output */
Press any key to continue . . .
.
- Follow-Ups:
- Re: Quicksort
- From: cr88192
- Re: Quicksort
- References:
- Quicksort
- From: Roman Töngi
- Re: Quicksort
- From: Adak
- Re: Quicksort
- From: robertwessel2@xxxxxxxxx
- Re: Quicksort
- From: cr88192
- Re: Quicksort
- From: robertwessel2@xxxxxxxxx
- Re: Quicksort
- From: cr88192
- Re: Quicksort
- From: user923005
- Re: Quicksort
- From: cr88192
- Re: Quicksort
- From: user923005
- Re: Quicksort
- From: cr88192
- Re: Quicksort
- From: cr88192
- Re: Quicksort
- From: user923005
- Re: Quicksort
- From: cr88192
- Quicksort
- Prev by Date: Re: Quicksort
- Next by Date: Re: A note on computing thugs and coding bums
- Previous by thread: Re: Quicksort
- Next by thread: Re: Quicksort
- Index(es):
