Python DSA Series 08: A Guide to Sorting Algorithms

Python DSA Series 08: A Guide to Sorting Algorithms

Welcome to the final post in our Python DSA series! We’ve come a long way, from basic lists to complex graphs. We conclude with one of the most fundamental problems in computer science: sorting. Sorting is a critical prerequisite for many efficient algorithms, including the binary search we just learned about.

While you’ll often just use Python’s built-in list.sort() or sorted(), understanding the algorithms behind them is essential for a complete computer science foundation.

1. Bubble Sort: The Educational Example

Bubble Sort is the classic introductory sorting algorithm. It’s simple to understand but too slow for most practical applications.

• Concept: Repeatedly step through the list, compare each pair of adjacent items, and swap them if they are in the wrong order. Passes are repeated until no swaps are needed, indicating the list is sorted. The largest elements “bubble” up to the end of the list.

Python Implementation

def bubble_sort(data):
    n = len(data)
    for i in range(n):
        # A flag to optimize if the list is already sorted
        swapped = False
        for j in range(0, n - i - 1):
            if data[j] > data[j + 1]:
                # Swap the elements
                data[j], data[j + 1] = data[j + 1], data[j]
                swapped = True
        if not swapped:
            break # List is sorted, no need for more passes
    return data

# Example
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)
print(f"Sorted list is: {my_list}")

• Time Complexity: O(n²) in the average and worst cases.
• Space Complexity: O(1) - It sorts in-place.

---

2. Merge Sort: The Reliable Divide and Conquer

Merge Sort is a highly efficient, stable, and reliable sorting algorithm. It’s a perfect example of the Divide and Conquer strategy.

• Concept:
  1. Divide: Recursively split the list in half until you have sublists of size 1 (which are inherently sorted).
  2. Conquer: Merge the sorted sublists back together in the correct order until you have one, fully sorted list.

Python Implementation

def merge_sort(data):
    if len(data) > 1:
        mid = len(data) // 2
        left_half = data[:mid]
        right_half = data[mid:]

        # Recursively sort both halves
        merge_sort(left_half)
        merge_sort(right_half)

        # Merge the sorted halves
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                data[k] = left_half[i]
                i += 1
            else:
                data[k] = right_half[j]
                j += 1
            k += 1

        # Check for any leftover elements
        while i < len(left_half):
            data[k] = left_half[i]
            i += 1
            k += 1
        while j < len(right_half):
            data[k] = right_half[j]
            j += 1
            k += 1
    return data

# Example
my_list = [38, 27, 43, 3, 9, 82, 10]
merge_sort(my_list)
print(f"Sorted list is: {my_list}")

• Time Complexity: A consistent O(n log n) for all cases (best, average, and worst).
• Space Complexity: O(n), as it requires extra arrays to store the halves during the merge step.

---

3. Quick Sort: The Fast but Unstable

Quick Sort is another Divide and Conquer algorithm. It’s often faster in practice than Merge Sort, but its worst-case performance is worse.

• Concept:
  1. Partition: Pick an element from the array (the pivot). Reorder the array so that all elements with values less than the pivot come before it, and all elements with values greater come after it.
  2. Recurse: Recursively apply the same logic to the sub-arrays on either side of the pivot.

Python Implementation

def quick_sort(data):
    if len(data) <= 1:
        return data
    else:
        pivot = data[len(data) // 2]
        left = [x for x in data if x < pivot]
        middle = [x for x in data if x == pivot]
        right = [x for x in data if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

# Example
my_list = [38, 27, 43, 3, 9, 82, 10]
sorted_list = quick_sort(my_list)
print(f"Sorted list is: {sorted_list}")

• Time Complexity:
  • Best and Average Case: O(n log n).
  • Worst Case: O(n²). This occurs if the pivot is consistently the smallest or largest element (e.g., when sorting an already-sorted list).
• Space Complexity: O(log n) on average for the recursion stack.

Timsort: The Algorithm Python Uses

Python’s built-in sort() method and sorted() function use Timsort. It’s a hybrid algorithm, cleverly combining Merge Sort and Insertion Sort. It is highly optimized for real-world data, which is often partially sorted. You don’t need to know how to implement it, but it’s good to know that Python uses a state-of-the-art algorithm under the hood.

Conclusion: The End of the Beginning

Congratulations! You’ve journeyed through the foundational Data Structures and Algorithms in Python. From the simple list to complex graphs, and from linear search to O(n log n) sorting, you now have the conceptual tools to analyze and solve a wide variety of programming problems.

This series is not the end, but the end of the beginning. The true path to mastery is practice. Take these concepts and apply them on platforms like LeetCode, HackerRank, or by building your own projects.

Happy coding!

Suggested Reading

• Sorting Algorithms (Wikipedia)
• Visualgo - Sorting - An amazing visualization tool for algorithms.
• Timsort (Wikipedia)