Shell Sort

Size
Speed

Description

This algorithm works by sorting elements far from each other.

Then reducing the gap between the elements to be compared.

Since it starts with far-apart elements, it's fast at moving out of place elements into place quickly.

Complexity

Time
  • Best Case
  • Worst Case
  • Average Case
  • O(nlogn)
  • O(n^2)
  • O(nlogn)
Space
  • O(1)

Implementation

function shellSort(arr) {

  let h = 1;
  while (h < arr.length / 3) {
    h = 3 * h + 1;
  }

  while (h >= 1) {

    for (let i = h; i < arr.length; i++) {
      for (let j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
        [arr[j], arr[j - h]] = [arr[j - h], arr[j]];
      }
    }

    h = Math.floor(h / 3);
  }

}