Shell Sort Algorithm in DSA Go - 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.

func shellSort(arr []int) {
  n := len(arr)
  for gap := n / 2; gap > 0; gap /= 2 {
    for i := gap; i < n; i++ {
      temp := arr[i]
      j := i
      for 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 that repeat work:

• Primary operation: The inner loop that shifts elements by the current gap.
• How many times: The outer loop reduces gap roughly by half each time, and the inner loops run over the array for each gap.

How Execution Grows With Input

As the list size grows, the number of comparisons and shifts depends on the gap sequence.

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, depending on gap choices.

Final Time Complexity

Time Complexity: O(n^{1.5})

This means the time grows faster than a simple list scan but much slower than checking every pair.

Common Mistake

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

[OK] Correct: Shell Sort uses gaps to reduce comparisons, so it usually runs faster than simple quadratic sorts.

Interview Connect

Understanding Shell Sort's time complexity shows you how clever ideas can improve sorting speed beyond simple methods.

Self-Check

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