Lesson 4 — Advanced

Sorting: Merge, Quick, Counting, Radix

Sorting algorithms DSA ka foundation hai. Comparison-based sorts (merge, quick) O(n log n) pe limit hain, jabki non-comparison sorts (counting, radix) O(n) tak ja sakte hain khaas cases mein.

Comparison vs Non-Comparison Sorts

Sorting algorithms do categories mein aate hain:

• Comparison Sorts — Elements ko compare karke sort karte hain. Lower bound: O(n log n). Examples: Merge Sort, Quick Sort, Heap Sort, Insertion Sort.
• Non-Comparison Sorts — Compare nahi karte, keys ka properties use karte hain. O(n) tak ja sakte hain. Examples: Counting Sort, Radix Sort, Bucket Sort.

Interview mein sabse zyada puchhe jaate hain: Merge Sort, Quick Sort, Counting Sort. Inhe deeply samjho.

Merge Sort: Divide and Conquer

Merge sort array ko do halves mein break karta hai, recursively sort karta hai, phir merge karta hai. Stable sort hai — equal elements ka relative order preserve hota hai.

Steps:

1. Array ko mid pe todo.
2. Left half ko recursively sort karo.
3. Right half ko recursively sort karo.
4. Dono sorted halves ko merge karo.

Merge Sort Visualization:

 [38, 27, 43, 3, 9, 82, 10]
 / \
 [38, 27, 43, 3] [9, 82, 10]
 / \ / \
 [38, 27] [43, 3] [9, 82] [10]
 / \ / \ / \ |
 [38] [27] [43] [3] [9] [82] [10]
 \ / \ / \ / |
 [27, 38] [3, 43] [9, 82] [10]
 \ / \ /
 [3, 27, 38, 43] [9, 10, 82]
 \ /
 [3, 9, 10, 27, 38, 43, 82]

Time: O(n log n) always
Space: O(n) — extra array chahiye
Stable: Yes

Code: Merge Sort

def merge_sort(arr):
 if len(arr) <= 1:
 return arr

 mid = len(arr) // 2
 left = merge_sort(arr[:mid])
 right = merge_sort(arr[mid:])

 return merge(left, right)


def merge(left, right):
 result = []
 i = j = 0

 while i < len(left) and j < len(right):
 if left[i] <= right[j]:
 result.append(left[i])
 i += 1
 else:
 result.append(right[j])
 j += 1

 # Baaki elements add karo
 result.extend(left[i:])
 result.extend(right[j:])
 return result


# Example
arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))
# Output: [3, 9, 10, 27, 38, 43, 82]

Quick Sort: Partition-Based

Quicksort ek pivot choose karta hai, array ko partition karta hai (chote elements left, bade right), phir recursively sort karta hai. In-place sort hai — extra space nahi chahiye.

Pivot selection sabse important hai. Agar pivot hamesha middle element ho toh average case O(n log n) hai. Worst case O(n—) hai jab pivot sabse chota ya bada ho (already sorted array).

Quick Sort Visualization:

Array: [10, 80, 30, 90, 40, 50, 70]
Pivot: 70 (last element)

Partition:
 [< 70] 70 [> 70]
 [10, 30, 40, 50] 70 [80, 90]

Recursively sort:
 Left: [10, 30, 40, 50] ✓ pivot 50 ? [10, 30, 40] 50
 Right: [80, 90] ✓ already sorted

Final: [10, 30, 40, 50, 70, 80, 90]

Time: O(n log n) average, O(n—) worst
Space: O(log n) — recursion stack
Stable: No (in-place partition mein order change hota hai)

Code: Quick Sort

def quick_sort(arr):
 if len(arr) <= 1:
 return arr

 pivot = arr[len(arr) // 2]
 left = [x for x in arr if x < pivot]
 middle = [x for x in arr if x == pivot]
 right = [x for x in arr if x > pivot]

 return quick_sort(left) + middle + quick_sort(right)


# In-place version (Lomuto partition)
def quick_sort_inplace(arr, low, high):
 if low < high:
 pi = partition(arr, low, high)
 quick_sort_inplace(arr, low, pi - 1)
 quick_sort_inplace(arr, pi + 1, high)


def partition(arr, low, high):
 pivot = arr[high]
 i = low - 1

 for j in range(low, high):
 if arr[j] <= pivot:
 i += 1
 arr[i], arr[j] = arr[j], arr[i]

 arr[i + 1], arr[high] = arr[high], arr[i + 1]
 return i + 1


# Example
arr = [10, 80, 30, 90, 40, 50, 70]
print(quick_sort(arr))
# Output: [10, 30, 40, 50, 70, 80, 90]

Counting Sort: Non-Comparison

Counting sort comparison use nahi karta. Agar elements known range mein hain (jaise 0-9), toh frequency count karo aur direct placement karo. O(n + k) time — n = elements, k = range.

Code: Counting Sort

def counting_sort(arr):
 if not arr:
 return arr

 max_val = max(arr)
 min_val = min(arr)
 range_val = max_val - min_val + 1

 # Frequency array banao
 count = [0] * range_val
 output = [0] * len(arr)

 # Count occurrences
 for num in arr:
 count[num - min_val] += 1

 # Cumulative count
 for i in range(1, len(count)):
 count[i] += count[i - 1]

 # Build output (reverse traversal for stability)
 for num in reversed(arr):
 count[num - min_val] -= 1
 output[count[num - min_val]] = num

 return output


# Example
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr))
# Output: [1, 2, 2, 3, 3, 4, 8]

Radix Sort

Radix sort digits ke hisaab se sort karta hai — pehle ones place, phir tens, phir hundreds. Har pass mein Counting Sort use hota hai as subroutine. O(d * (n + k)) time — d = digits, n = elements, k = base (10 for decimal).

Time Complexity Comparison

Algorithm Best Average Worst Space Stable
-----------------------------------------------------------------
Bubble Sort O(n) O(n—) O(n—) O(1) Yes
Insertion Sort O(n) O(n—) O(n—) O(1) Yes
Merge Sort O(nlogn) O(nlogn) O(nlogn) O(n) Yes
Quick Sort O(nlogn) O(nlogn) O(n—) O(logn) No
Heap Sort O(nlogn) O(nlogn) O(nlogn) O(1) No
Counting Sort O(n+k) O(n+k) O(n+k) O(n+k) Yes
Radix Sort O(dn) O(dn) O(dn) O(n+k) Yes

Interview mein yaad rakho:
- Default: Merge Sort (guaranteed O(n log n), stable)
- Space constraint: Quick Sort (in-place)
- Small range integers: Counting Sort (O(n))
- Digits-based: Radix Sort

Try it: code khud likho

Common Mistakes

• Quick sort mein pivot galat choose karna — Hamesha middle ya random pivot lo. First/last element lo toh sorted array pe O(n—) hoga.
• Merge sort mein space bhoolna — Merge sort O(n) extra space leta hai. Interview mein batao agar space constraint hai toh merge sort mat use karo.
• Counting sort ka range assume karna — Counting sort sirf tab kaam karta hai jab range known aur reasonable ho. Agar max element 10^9 hai toh memory overflow hoga.
• Stability importance — Jab objects sort karo (jaise students by marks), stability important hai. Merge sort stable hai, quick sort nahi.
• Built-in sort use karna interview mein — Interview mein arr.sort() ya sorted() mat karo unless explicitly allowed. Algorithm implement karo.