Shell Sort Algorithm In Javascript

Learn what is a shell sort algorithm and how to implement it in Javascript.

List of sorting algorithm

• Bubble sort algorithm in javascript
• Insertion sort algorithm in javascript
• Selection sort in javascript
• Merge sort in javascript
• Quick sort in javascript
• Counting sort in javascript
• Radix sort in javascript
• Bucket sort in javascript
• Heap sort in javascript

What is shell sort?

Developed by Donald shell in 1959, shell sort also known as shell’s method is an in-place comparison sort. It can either be a generalization of sorting by exchange(bubble sort) or sorting by insertion(insertion sort).

It starts by sorting a pair of elements that are far apart from each other and then gradually reducing the interval. By starting with far apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange.

The performance of shell sort is heavily dependent on the sequence used to gradually decrease the intervals between elements.

Some of the optimal sequence used are:

• Shell’s original sequence: N/2 , N/4 , …, 1
• Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2
• Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1
• Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,...
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....

---

How shell sort works?

1. Suppose we are sorting this array [9, 8, 3, 7, 5, 6, 4, 1].

2. We are using the shell’s original sequence (N/2, N/4, ...1) as intervals in our algorithm.

The length of the above array is N=8 thus using the above sequence elements at interval N/2 = 8/2 = 4 will be compared and swapped if they are not in order.

This process goes on for all the elements in the first cycle.

3. In the cycle the interval will be N/4 = 8/4 = 2. Thus every second will be compared and swapped if they are in different orders.

4. Keep on repeating this till the interval is greater than or equal to 1.

shellSort(array, size)
  for interval i <- size/2n down to 1
    for each interval "i" in array
        sort all the elements at interval "i"
end shellSort

---

Shell sort algorithm in Javascript.

const shellSort = (arr, n = arr.length) => {
  //Reduce the interval in each cycle
  for (let interval = n / 2; interval > 0; interval /= 2) {
    //Sort the element using insertion sort in each cycle.
    for (let i = interval; i < n; i += 1) {
      let temp = arr[i];
      let j;
      for (j = i; j >= interval && arr[j - interval] > temp; j -= interval) {
        arr[j] = arr[j - interval];
      }
      arr[j] = temp;
    }
  }
}

Input:
const arr = [9, 8, 3, 7, 5, 6, 4, 1];
shellSort(arr);
console.log(arr);

Output:
[1, 3, 4, 5, 6, 7, 8, 9]

Time complexity of shell sort algorithm

Shell sort is a unstable sorting algorithm because it does not examine the elements lying in between the intervals.

Worst case: O(n ^ 2)

According to Poonen Theorem, worst case complexity for shell sort is Θ(Nlog N)2/(log log N)2) or Θ(Nlog N)2/log log N) or Θ(N(log N)2) or something in between.

Average case: O(nlogn)

When the array is already sorted, the total number of comparisons for each interval (or increment) is equal to the size of the array.

Best case: O(nlogn)

Same as the average case.

---

Space complexity

As shell sort is an in-place comparison sort algorithm, it requires constant space O(1).

---

Applications of shell sort

Shell sort is used:

• When calling a stack is overhead.
• When recursion exceeds a limit.
• When Insertion sort does not perform well when the close elements are far apart. It helps in reducing the distance between the close elements.