[prev] 35 [next]

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