Understanding Shell Sort Algorithm: Step-by-Step in JavaScript ??

Shell sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of ShellSort is to allow the exchange of far items. In Shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.

Algorithm:

1. Start
2. Initialize the value of gap size, say h.
3. Divide the list into smaller sub-part. Each must have equal intervals to h.
4. Sort these sub-lists using insertion sort.
5. Repeat this step 2 until the list is sorted.
6. Print a sorted list.
7. Stop.

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

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

      let j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
        arr[j] = arr[j - gap];

      arr[j] = temp;
    }
  }
  return arr;
}

const arr = [64, 25, 12, 22, 11];
console.log("Original Array:", arr);
const sortedArray = shellSort(arr);
console.log("Sorted Array:", sortedArray);