Appendix B — Correspondence

From time to time I get interesting emails about Combsort.

Date: Wed, 05 Mar 2003 12:33:36 -0800
From: David B Ring <dbring@pacbell.net>
To: wconrad@yagni.com
Subject: simpler faster CombSort

Enjoyed your pages comparing CombSort in various languages.

I use InsertionSort to finish for QuickSort and to build initial runs for
MergeSort.  The same trick allows a simpler CombSort without the Swapped
flag or special handling for Gap values of 9/10/11.  Just stop when Gap < 9
and do one pass of InsertionSort.  I find this is 10-15% faster than the
original CombSort11 algorithm.  Java version:

public void CombSort(int[] a) {
        int n = a.length(), gap, i, j, tmp;

        gap = n;
        do {
                gap = (10 * gap) / 13;
                for (i = 0; i <= n - gap; ++i) {
                        j = i + gap;
                        if (a[i] > a[j]) {tmp = a[i]; a[i] = a[j]; a[j] =
tmp;}
                }
        } while (gap > 8);
        InsertionSort(a);
}

public void InsertionSort(int[] a) {
        int n = a.length(), i, j;

        for (i = 1; i <= n; ++i) {
                tmp = a[i];
                for (j = i - 1; j >= 0; --j) {if (tmp < a[j]) a[j + 1] =
a[j]; else break;}
                a[j + 1] = tmp;
        }
}

Dave Ring

Date: Thu, 6 Mar 2003 10:01:30 -0800
From: David B Ring <dbring@pacbell.net>
To: Wayne Conrad <wconrad@yagni.com>
Subject: Re: simpler faster CombSort

Feel free to add the hybrid CombSort to the article.  You can add my
email address if you like, but I don't have a home page to link to.

The simplicity of CombSort is very attractive, but I find that other
sorts are really significantly faster.  Sorting 500,000 random strings
with well-tweaked Java versions of various sorts, I get CombSort 19.6
seconds, HeapSort 7.6, MergeSort 3.8, QuickSort 3.8, Ternary QuickSort
2.7 and MSD RadixSort 0.98.  Merge and Radix are my favorites, since
they're stable and have no worst case vulnerabilities.

Dave

On Wednesday, March 5, 2003, at 05:04  PM, Wayne Conrad wrote:

>On Wed, Mar 05, 2003 at 12:33:36PM -0800, David B Ring wrote:
>>Enjoyed your pages comparing CombSort in various languages.
>
>David, Thanks!  Switch to insertion sort is a neat idea.  Would you
>mind if I add your email to the article, either in the main page or as
>a linked page?  I can either include, exclude, or obscure your email
>address (or include a link to your home page, or whatever else you'd
>like).  Just let me know whether I can do this and how you'd like to
>be credited.
>
>        Wayne Conrad
>