How To Do Shell Sort in JavaScript

Shell Sort is an extension of Insertion Sort that improves performance by allowing the exchange of far-apart elements. This sorting algorithm is named after its inventor, Donald Shell. It works by sorting elements at a specific interval or gap, which gradually decreases until it becomes 1. At this point, Shell Sort behaves like Insertion Sort, but with the advantage of having already moved elements closer to their final position.

This post will explore how to implement Shell Sort in JavaScript, explain the algorithm step-by-step, and discuss its advantages and limitations.

What is Shell Sort?

Shell Sort is a generalized version of Insertion Sort. While Insertion Sort works well when elements are almost sorted, Shell Sort improves performance by comparing and swapping far-apart elements, reducing the number of comparisons and shifts. Shell Sort starts with a large gap between elements and then progressively reduces this gap, ultimately performing a final pass with a gap of 1 (like Insertion Sort).

Pseudocode for Shell Sort

Here’s the basic pseudocode for Shell Sort:

procedure shellSort(arr)
    n = length(arr)
    gap = n / 2

    while gap > 0 do
        for i = gap to n - 1 do
            temp = arr[i]
            j = i

            // Shift earlier gap-sorted elements up until the correct location is found
            while j >= gap and arr[j - gap] > temp do
                arr[j] = arr[j - gap]
                j = j - gap

            arr[j] = temp
        gap = gap / 2

• Step-by-Step Explanation:
  • The gap starts as half the array length and gradually reduces by dividing by 2.
  • For each gap, perform an Insertion Sort for the elements that are gap distance apart.
  • As the gap decreases, the array becomes increasingly sorted until the final pass with a gap of 1.

Time Complexity of Shell Sort

The time complexity of Shell Sort depends heavily on the gap sequence used. For the commonly used Shell’s original gap sequence (n/2, n/4, n/8,…), the complexity is approximately O(n²). However, other gap sequences can provide better performance.

• Best Case: O(n log n) – With optimal gap sequences, Shell Sort can approach O(n log n) for nearly sorted arrays.
• Average Case: O(n^1.5) – For common gap sequences, the average complexity is about O(n^1.5).
• Worst Case: O(n²) – In the worst case, Shell Sort can degrade to O(n²), similar to Insertion Sort.

Space Complexity of Shell Sort

• Space Complexity: O(1) – Shell Sort is an in-place sorting algorithm, meaning it sorts the array without requiring additional memory, apart from a few variables.

JavaScript Implementation of Shell Sort

Here’s the JavaScript code to implement Shell Sort:

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

    // Start with a gap of half the array length, then reduce the gap
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // Perform a gapped insertion sort
        for (let i = gap; i < n; i++) {
            let temp = arr[i];
            let j;

            // Shift elements that are gap distance apart
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }

            // Place the temp element at its correct position
            arr[j] = temp;
        }
    }
    return arr;
}

// Example usage
const arr = [12, 34, 54, 2, 3];
console.log("Initial array:", arr);
console.log("Sorted array:", shellSort(arr));

Output:

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

Explanation:

• The gap starts as half the array length (Math.floor(n / 2)), and we keep reducing it by half (gap = Math.floor(gap / 2)).
• For each gap, we perform a modified Insertion Sort, where we compare elements that are gap distance apart and move them to their correct position.
• This process continues until the gap becomes 1 and the array is fully sorted.

Step-by-Step Walkthrough of Shell Sort

Let’s walk through Shell Sort using the array [12, 34, 54, 2, 3].

Step 1: First Pass with Gap 2

• Initial gap: 2 (half the array length).
• Compare and rearrange elements 2 positions apart:
  • Compare 12 and 54 (no change).
  • Compare 34 and 2 (swap them).
• Array after the first pass: [12, 2, 54, 34, 3]

---

Step 2: Second Pass with Gap 1

• Next gap: 1 (now Shell Sort behaves like Insertion Sort but with the benefit of having moved some elements closer to their final positions).
• Compare adjacent elements:
  • Compare 12 and 2 (swap them). Array: [2, 12, 54, 34, 3].
  • Compare 12 and 54 (no change).
  • Compare 54 and 34 (swap them). Array: [2, 12, 34, 54, 3].
  • Compare 54 and 3 (swap them). Array: [2, 12, 34, 3, 54].

---

Step 3: Final Pass with Gap 1 (Corrected)

• Continue with gap 1:
  • Compare 34 and 3 (swap them). Array: [2, 12, 3, 34, 54].
  • Now compare 12 and 3 (swap them). This places 12 in the correct position. Array: [2, 3, 12, 34, 54].

At the end of this pass, the array is fully sorted.

Final Sorted Array: [2, 3, 12, 34, 54]

Pros and Cons of Using Shell Sort

Pros:

1. Efficient for Medium-Sized Datasets: Shell Sort can outperform simpler algorithms like Bubble Sort or Insertion Sort on medium-sized datasets.
2. In-Place Sorting: With a space complexity of O(1), it doesn’t require additional memory.
3. Simple to Implement: Shell Sort is easy to code and understand.
4. Handles Nearly Sorted Arrays Well: Shell Sort excels when dealing with partially or nearly sorted arrays.

Cons:

1. Not the Fastest for Large Datasets: Although Shell Sort improves upon Insertion Sort, it is generally outperformed by advanced algorithms like Quick Sort or Merge Sort on large datasets.
2. Sensitive to Gap Sequence: The performance of Shell Sort can vary significantly based on the gap sequence used.

When to Use Shell Sort

Shell Sort is a good choice when:

1. You need an in-place sorting algorithm: With O(1) extra memory, Shell Sort works well in environments where memory usage is a concern.
2. You want something faster than Insertion Sort: Shell Sort is an improvement over Insertion Sort, making it useful for medium-sized datasets.
3. Handling nearly sorted arrays: If you know the array is almost sorted, Shell Sort can be particularly efficient.

However, algorithms like Merge Sort or Quick Sort are better choices for large datasets or if you need guaranteed O(n log n) performance.

Conclusion

Shell Sort is a simple and efficient sorting algorithm that improves upon Insertion Sort by introducing a gap-based comparison. It works well on medium-sized datasets and nearly sorted arrays. While its performance is sensitive to the choice of gap sequence, it provides a solid improvement over simpler sorting algorithms like Bubble Sort and Insertion Sort. However, Quick Sort or Merge Sort may be better suited for larger datasets or when more consistent performance is needed.

Congratulations on reading to the end of the tutorial!

Read the following articles to learn how to implement Shell Sort:

In Python – How to do Shell Sort in Python

In C++ – How to Do Shell Sort in C++

Have fun and happy researching!