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! 🧠📈