Part 6: Sorting Algorithms in Python – Concepts, Code, and Complexity

🚀 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

🧠 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

✅ 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
 
 

💬 Have a sorting trick or a favorite sorting bug story? Drop it in the comments and let’s learn together! 🧠📈