Shell Sort Algorithm in DSA Javascript - Time & Space Complexity

Time Complexity: Shell Sort Algorithm

O(n^{1.5})

Understanding Time Complexity

We want to understand how the time taken by Shell Sort changes as the list size grows.

How does the number of steps increase when sorting bigger lists?

Scenario Under Consideration

Analyze the time complexity of the following Shell Sort code.

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++) {
      let temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
}
    

This code sorts an array by comparing elements far apart and gradually reducing the gap.

Identify Repeating Operations

Look at the loops and repeated comparisons.

• Primary operation: The inner while loop that shifts elements to insert the current element in the right place.
• How many times: This depends on the gap and how many elements need shifting; it repeats for each element and for each gap size.

How Execution Grows With Input

As the list grows, the number of comparisons and shifts grows too, but not as fast as simple sorting methods.

Input Size (n)	Approx. Operations
10	About 20-30 operations
100	Few thousands of operations
1000	Hundreds of thousands of operations

Pattern observation: The operations grow faster than linear but slower than quadratic, improving efficiency over simple sorts.

Final Time Complexity

Time Complexity: O(n^{1.5})

This means the time grows faster than the list size but much slower than simple sorting methods like bubble sort.

Common Mistake

[X] Wrong: "Shell Sort always runs in quadratic time like bubble sort."

[OK] Correct: Shell Sort uses gaps to reduce the number of shifts, so it usually runs faster than quadratic time, especially on larger lists.

Interview Connect

Understanding Shell Sort's time complexity shows you how clever ideas can improve sorting speed, a useful skill for solving real problems efficiently.

Self-Check

"What if we changed the gap sequence to use a different pattern, like the Knuth sequence? How would the time complexity change?"