🚀 Introduction
Sorting is a fundamental operation in programming — and mastering sorting algorithms helps you understand time complexity, algorithm design, and even how Python’s built-in tools work under the hood.
In this post, we’ll explore:
✅ Basic and advanced sorting algorithms
✅ Python implementations with step-by-step logic
✅ When to use each sorting method
✅ Built-in sorting (sorted(), list.sort()) and how it's optimized
✅ Time & space complexity comparison
📚 1️⃣ Why Sorting Matters
Sorting is used everywhere:
1. Organizing data before searching (e.g., binary search)
2. Making duplicate detection easier
3. Efficient comparisons, merging, and filtering
4. Preprocessing before solving harder problems (e.g., greedy, DP)💡 2️⃣ Built-in Sorting in Python
🔹 sorted() – returns a new sorted list
nums = [5, 2, 9, 1]
sorted_nums = sorted(nums)🔹 list.sort() – sorts in place
nums.sort()✅ Both use Timsort, a hybrid of merge and insertion sort
🕒 Time complexity: O(n log n) (worst-case)
🧮 3️⃣ Selection Sort – Simple but Inefficient
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_i = i
for j in range(i + 1, n):
if arr[j] < arr[min_i]:
min_i = j
arr[i], arr[min_i] = arr[min_i], arr[i]
return arr📦 Time: O(n²)
✅ Easy to understand
❌ Not suitable for large data
🔁 4️⃣ Bubble Sort – Compare and Swap
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr📦 Time: O(n²)
✅ Good for teaching purposes
❌ Inefficient for real-world use
🧊 5️⃣ Insertion Sort – Builds Sorted Portion
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr📦 Time: O(n²), but efficient for small or nearly sorted arrays
✅ Used in Timsort for small runs
🧬 6️⃣ Merge Sort – Divide and Conquer
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 = []
l = r = 0
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result.extend(left[l:])
result.extend(right[r:])
return result📦 Time: O(n log n)
🧠 Space: O(n)
✅ Stable, consistent
✅ Great for linked lists or external sorting
⚡ 7️⃣ Quick Sort – Efficient and Elegant
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
more = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(more)📦 Time:
Average: O(n log n)
Worst: O(n²) (rare, with bad pivots)✅ Fast and in-place (with extra work)
❌ Unstable
📊 8️⃣ Comparison Table
| Algorithm | Time Complexity | Space | Stable? Use When |
|---|---|---|---|
| Selection Sort | O(n²) | O(1) | ❌ |
| Bubble Sort | O(n²) | O(1) | ✅ |
| Insertion Sort | O(n²), Best: O(n) | O(1) | ✅ |
| Merge Sort | O(n log n) | O(n) | ✅ |
| Quick Sort | O(n log n), Worst O(n²) | O(log n) | ❌ |
| Timsort (Python) | O(n log n) | O(n) | ✅ |
🧠 Real-World Tips
✅ For large unsorted datasets → Timsort (default)
✅ For small arrays or known order → Insertion Sort
✅ For linked lists → Merge Sort
✅ For interview practice → Quick Sort is a favorite
🧪 Practice Problems
| Problem | Technique |
|---|---|
| Sort Colors (Dutch Flag) | Custom in-place sort |
| Merge Intervals | Sorting + merging |
| Top K Frequent Elements | Sorting by frequency |
| Largest Number | Custom sort with key |
| Kth Largest Element | Quickselect |
✅ Summary
✔️ Sorting algorithms vary in efficiency, stability, and use cases
✔️ Learn basic ones for intuition, master advanced ones for performance
✔️ Python uses Timsort, a hybrid of merge and insertion sort
✔️ In interviews, know when and why to choose a specific algorithm
🔜 Coming Up Next:
👉 Part 7: Searching Algorithms – Binary Search and Its Powerful Variants
We’ll cover:
1. Linear vs Binary Search
Binary search templates
Search in rotated array
Lower/upper bounds
Real-world applications