Originally Posted by

**rcgldr**
If the array is large enough, then a "natural" bottom up merge sort would be fast, but it uses a second array for temporary storage, and could require a final copy array step if the the result has to be in the original array (as opposed to the second array).

Actually, johnmerlino is right. Insertion sort is **the** fastest algorithm for an almost sorted array (depending on your exact definition of "almost").

It doesn't even depend on how big or small the array is either. If the array is actually sorted, then for a good implementation the amount of work it does is equal to the amount of work required to determine if the array is sorted. Not just in terms of big-oh notation either, but in terms of actual CPU instructions executed.

Some other useful tips:

1. Shell Sort, as per how Donald Shell wrote it (with gap sizes that halve each time), is actually a very poor choice of gaps. The Incerpj-Sedgewick gap-table variation is far superior.

2. You can simply write your insertion sort such that instead of using ++, --, -1, +1, or 1, that you instead use += k, -= k, -k, +k, and k, where k is another parameter. Then if you call it with k==1 you get a regular insertion sort, or if you call, it from within a Shell Sort skeleton function, then you get a Shell Sort. I.e. the same code does both.

3. Shell Sort is, as you know, doing insertions, i.e. rather than inserting via repeated swapping, just do it via insertion as you would with Insertion Sort.

Since I'm feeling generous, here's a version of some of the C++ code I have, converted to C, to illustrate the idea:
Code:

void ShellSortAux(int a[], int n, int k) {
for (int i = k; i < n; ++i) {
int j = i - k;
if (a[i] < a[j]) {
int tempItem = a[i];
do {
a[j+k] = a[j];
j-=k;
} while ((j >= 0) && (tempItem < a[j]));
a[j+k] = tempItem;
}
}
}
//Donald Shell 1959
void OriginalShellSort(int a[], int n) {
for (int m = n/2; m > 0; m/=2)
ShellSortAux(a, n, m);
}
//Incerpi-Sedgewick 1985
void ShellSortIncerpiSedgewick(int a[], int n) {
const int incs[] = {
1, 3, 7, 21, 48, 112,
336, 861, 1968, 4592, 13776,
33936, 86961, 198768, 463792, 1391376,
3402672, 8382192, 21479367, 49095696, 114556624,
343669872, 52913488, 2085837936};
for (int l = sizeof(incs)/sizeof(incs[0]); l > 0;)
ShellSortAux(a, n, incs[--l]);
}

You'll find this a lot quicker than what you have, and as a result, you may find you don't care so much about detecting the almost-sorted case any more.

(More info on my website)