ShellSort: Improving Insertion Sort
Insertion sort:
- based on exchanges that only involve adjacent items
- already improved above by using moves rather than swaps
- "long distance" moves may be more efficient
Shellsort: basic idea
- array is h-sorted if taking every h'th element yields a sorted array
- an h-sorted array is made up of n/h interleaved sorted arrays
- Shellsort: h-sort array for progressively smaller h, ending with 1-sorted
|