shell sort question

[fuerchter]

Hey there,
I just wrote my own version of insertion sort and thought I might pick another random sorting algorithm to write in C++. When I looked at the wikipedia page of shell sort (http://en.wikipedia.org/wiki/Shell_sort ) it said that it uses insertion sort. It splits up the array first and performs insertion sort on each sequence.

My problem with this though is the last gap shown on the wikipedia page which is 1 in this case. If you are performing insertion sort on the whole array in the end (as I said, the gap is 1 so every single value in the array is effected) it is going to be sorted anyways, right? I mean, why would you perform the sort on it with gaps of 5 and 3 only to later execute a process that would have sorted it without the help of the previous steps :S

I don't know, I'm probably wrong but it seems redundant to me. Can anyone clear this up for me? ^^
greetings

[Peter87]

Wikipedia wrote:

As the example illustrates, the subarrays that Shellsort operates on are initially short; later they are longer but almost ordered. In both cases insertion sort works efficiently.

In the worst case (happens when all elements are ordered in reversed order) insertion sort is quite slow so if used directly it could take a long time. Insertion sort is on the other hand very fast if the elements are nearly sorted (if already sorted, insertion sort only need to pass through the elements once). When Shellsort is doing the last insertion sort the elements is probably much more sorted than it was from the beginning making the insertion sort much faster.

Shellsort is far from always faster than using insertion sort directly but it avoids the terrible worst case of insertion sort. Often the worst case is what you care about. If something is fast enough in the worst case you know it's always fast enough.

[fuerchter]

Thanks, Peter that cleared it up nicely. Now I was actually able to write the shell sort algorithm too :D