SimuVedaAlgorithms Lab Open in the lab

Sorting / Intermediate

Shell Sort Visualizer

Insertion sort, but first on values that are gap apart. Big gaps move far-away values quickly; the last pass with gap 1 is a normal insertion sort on an almost sorted array.

Start the Shell Sort simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n log n)
Average timeO(n^1.3)
Worst timeO(n²)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Shell sort on 5 values. Start with a big gap and shrink it. [5, 1, 4, 2, 8]
  2. Gap 2: insertion-sort the values that are 2 apart.
  3. Compare a[0] = 5 with a[2] = 4, 2 apart.
  4. 5 is bigger, so swap them across the gap. [4, 1, 5, 2, 8]
  5. Compare a[1] = 1 with a[3] = 2, 2 apart.
  6. Compare a[2] = 5 with a[4] = 8, 2 apart.
  7. Gap 1: a plain insertion sort, but the array is now nearly sorted.
  8. Compare a[0] = 4 with a[1] = 1, 1 apart.
  9. 4 is bigger, so swap them across the gap. [1, 4, 5, 2, 8]
  10. Compare a[1] = 4 with a[2] = 5, 1 apart.
  11. Compare a[2] = 5 with a[3] = 2, 1 apart.
  12. 5 is bigger, so swap them across the gap. [1, 4, 2, 5, 8]
  13. Compare a[1] = 4 with a[2] = 2, 1 apart.
  14. 4 is bigger, so swap them across the gap. [1, 2, 4, 5, 8]
  15. Compare a[0] = 1 with a[1] = 2, 1 apart.
  16. Compare a[3] = 5 with a[4] = 8, 1 apart.
  17. Sorted. 9 comparisons and 4 swaps.

Try it with your own input →

Shell sort in Java, Python, C++, C and JavaScript

void shellSort(int[] a) {
  int n = a.length;
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i++) {
      int j = i;
      while (j >= gap && a[j - gap] > a[j]) {
        swap(a, j, j - gap);
        j -= gap;
      }
    }
  }
}
def shell_sort(a):
    n = len(a)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            j = i
            while j >= gap and a[j - gap] > a[j]:
                a[j], a[j - gap] = a[j - gap], a[j]
                j -= gap
        gap //= 2
void shellSort(vector<int>& a) {
  int n = a.size();
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i++) {
      int j = i;
      while (j >= gap && a[j - gap] > a[j]) {
        swap(a[j], a[j - gap]);
        j -= gap;
      }
    }
  }
}
void shellSort(int a[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i++) {
      int j = i;
      while (j >= gap && a[j - gap] > a[j]) {
        int t = a[j]; a[j] = a[j - gap]; a[j - gap] = t;
        j -= gap;
      }
    }
  }
}
function shellSort(a) {
  const n = a.length;
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      let j = i;
      while (j >= gap && a[j - gap] > a[j]) {
        [a[j], a[j - gap]] = [a[j - gap], a[j]];
        j -= gap;
      }
    }
  }
}

In an interview

The gap sequence decides the speed. Halving (n/2, n/4, …) is simple; Knuth’s 1, 4, 13, 40… or Ciura’s sequence are faster in practice. Compare its swaps with insertion sort on Reversed.

More sorting