JavaScript Program to Implement Shell Sort

This post shows how to implement Shell Sort in JavaScript — an optimized version of insertion sort that compares elements far apart first, gradually reducing the gap, to avoid the slow "shifting one step at a time" behavior of plain insertion sort.

Shell sort in JavaScript:

Explanation:
Shell sort starts by comparing elements that are far apart (using a "gap"), sorting those gapped sub-sequences with insertion sort logic, then progressively shrinking the gap until it becomes 1 — at which point it performs a final, much faster insertion sort pass, since the array is already nearly sorted by then. This avoids the large number of small shifts that make plain insertion sort slow on bigger arrays.

---

---

JavaScript Program to Implement Shell Sort

function shellSort(arr) {
  const n = arr.length;

  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      const temp = arr[i];
      let j = i;

      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = temp;
    }
  }

  return arr;
}

const numbers = [12, 34, 54, 2, 3];
console.log("Sorted array:", shellSort(numbers));

Output:

Sorted array: [ 2, 3, 12, 34, 54 ]

Shell sort is a nice example of how a small change to a simple algorithm (adding gaps) can meaningfully improve performance. Compare it with plain Insertion Sort to see the difference the gap sequence makes, or try different gap sequences yourself in our Code Runner.

---

Frequently Asked Questions About Shell Sort in JavaScript

What is the time complexity of shell sort?

Shell sort's time complexity depends on the gap sequence used — with the simple "divide by 2" sequence shown here, it runs in roughly O(n²) worst case, but performs significantly better than plain insertion sort in practice. More advanced gap sequences can bring it closer to O(n log n).

How is shell sort different from insertion sort?

Plain insertion sort only compares adjacent elements, so moving a small value from the end of the array to the beginning takes many small shifts. Shell sort first moves elements long distances using large gaps, which dramatically reduces the work needed in the final gap-1 pass.

Is shell sort a stable sorting algorithm?

No. Because shell sort compares and swaps elements that are far apart, it can change the relative order of equal elements, making it an unstable sort in its standard form.