Shell Sort

Sorting

avgO(n^1.5)worstO(n²)spaceO(1)

Start with 32 unsorted values

1 / 614

Code

function shellSort(a: number[]) {  for (let gap = Math.floor(a.length / 2); gap > 0; gap = Math.floor(gap / 2)) {    for (let i = gap; i < a.length; i++) {      const temp = a[i];      let j = i;      while (j >= gap && a[j - gap] > temp) {        a[j] = a[j - gap];        j -= gap;      }      a[j] = temp;    }  }  return a;}

procedure shellSort(A)  for gap ← ⌊n / 2⌋, ⌊gap / 2⌋, … while gap > 0 do    for i ← gap to n − 1 do      temp ← A[i]      j ← i      while j ≥ gap and A[j − gap] > temp do        A[j] ← A[j − gap]        j ← j − gap      end while      A[j] ← temp    end for  end for  return Aend procedure

Variables

n=32

Counters

comparisons: 0
shifts: 0

Size32

Distribution

Custom values2 to 150 whole numbers, each 1 to 999

seed 5

How it works

An insertion sort over interleaved sub-arrays: elements gap apart are sorted first, then the gap shrinks until it is 1. Early long-distance moves mean the final insertion-sort pass has very little left to do.

Complexity

Best: O(n log n)
Average: O(n^1.5)
Worst: O(n²)
Space: O(1)
Stable: No
In place: Yes

Shell Sort

How it works

Complexity

Search algorithms