Sorting Stability and When to Use Which Sort in DSA Go - Time & Space Complexity

Time Complexity: Sorting Stability and When to Use Which Sort

O(n log n)

Understanding Time Complexity

Sorting algorithms arrange data in order, but they differ in speed and behavior.

We want to understand how their running time changes as data size grows and when to pick each sort.

Scenario Under Consideration

Analyze the time complexity of different sorting algorithms.

// Example: Bubble Sort
func bubbleSort(arr []int) {
  n := len(arr)
  for i := 0; i < n-1; i++ {
    for j := 0; j < n-i-1; j++ {
      if arr[j] > arr[j+1] {
        arr[j], arr[j+1] = arr[j+1], arr[j]
      }
    }
  }
}

// Example: Merge Sort
func mergeSort(arr []int) []int {
  if len(arr) <= 1 {
    return arr
  }
  mid := len(arr) / 2
  left := mergeSort(arr[:mid])
  right := mergeSort(arr[mid:])
  return merge(left, right)
}

func merge(left, right []int) []int {
  result := []int{}
  i, j := 0, 0
  for i < len(left) && j < len(right) {
    if left[i] <= right[j] {
      result = append(result, left[i])
      i++
    } else {
      result = append(result, right[j])
      j++
    }
  }
  result = append(result, left[i:]...)
  result = append(result, right[j:]...)
  return result
}

This code shows Bubble Sort and Merge Sort, two common sorting methods with different speeds and stability.

Identify Repeating Operations

Look at the loops and recursion that repeat work.

• Bubble Sort: Nested loops comparing and swapping elements repeatedly.
• Merge Sort: Recursion splitting array and merging sorted parts.
• Dominant operation: Comparisons and swaps in Bubble Sort; recursive splitting and merging in Merge Sort.

How Execution Grows With Input

As input size grows, the work done changes differently for each sort.

Input Size (n)	Bubble Sort Operations	Merge Sort Operations
10	About 45 comparisons	About 30 comparisons
100	About 4,950 comparisons	About 664 comparisons
1000	About 499,500 comparisons	About 9,966 comparisons

Bubble Sort grows very fast (square of n), Merge Sort grows slower (n times log n).

Final Time Complexity

Time Complexity: O(n²) for Bubble Sort, O(n log n) for Merge Sort

Bubble Sort gets much slower as data grows; Merge Sort stays efficient even for large data.

Common Mistake

[X] Wrong: "All sorting algorithms are equally fast for any data size."

[OK] Correct: Some sorts like Bubble Sort slow down a lot with more data, while others like Merge Sort handle growth better.

Interview Connect

Knowing sorting speeds and stability helps you pick the right tool for the job and explain your choices clearly.

Self-Check

"What if we used Quick Sort instead of Merge Sort? How would the time complexity and stability change?"