AlgoVerse

Shell sort

Insertion sort on items gap positions apart, with gaps shrinking down to 1; far-away items get near their place early.

Insertion sort is very fast on a nearly sorted array, but an item far from its place has to walk there one position at a time. Shell sort fixes this with a gap: first it insertion-sorts the items that are gap positions apart, so items reach their rough place in long jumps. Then it halves gap and repeats, down to gap = 1, which is plain insertion sort, but on an array that is already nearly sorted.

Read the full explanation ↓
Input:
n=8PDF export

Eight mixed numbers: gaps 4, 2 and 1.

  1. def shell_sort(a):
  2. gap = len(a) // 2
  3. while gap > 0:
  4. for j in range(gap, len(a)):
  5. key = a[j]
  6. i = j - gap
  7. while i >= 0:
  8. if a[i] <= key:
  9. break
  10. a[i + gap] = a[i]
  11. i = i - gap
  12. a[i + gap] = key
  13. gap = gap // 2
  14. return a

Invariant: After the round with gap = g, every subsequence a[k], a[k+g], a[k+2g], … is sorted.

Start

350331422103144195276447

Local variables

Orange = changed in this step

a list

3533421014192744

Call stack

  1. shell_sort()line 1
Step 1 of 150
Black = gap · Orange = key stepcompare: 0/19 · gap: 0/4 · pick: 0/17 · shift: 0/7 · insert: 0/17

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • shift
    • insert
    • current input (n=8)
    02040608046810121416n = number of itemscomparisonsinsertshift
    Show as a table
    ncomparisonsshiftinsert
    462.85
    611.65.98
    821.1717
    1029.111.322
    1237.816.726
    144419.431
    1668.726.849
    Explanation

    The idea

    Insertion sort is very fast on a nearly sorted array, but an item far from its place has to walk there one position at a time. Shell sort fixes this with a gap: first it insertion-sorts the items that are gap positions apart, so items reach their rough place in long jumps. Then it halves gap and repeats, down to gap = 1, which is plain insertion sort, but on an array that is already nearly sorted.

    Cost

    • With the gaps n/2, n/4, …, 1 the worst case is O(n²), but in practice it does much better than insertion sort.
    • With better sequences (for example 1, 4, 13, 40, …) the time drops to about O(n^1.5).
    • Extra memory O(1); it is not stable.

    What to watch in the trace

    • Use the "every loop round" detail level to see only the changes of gap.
    • Compare the "sorted backwards" input with insertion sort on the same input (the number of shift steps).