How do you implement a sorting algorithm in Python?

Python provides powerful built-in sorting mechanisms, but understanding how to implement sorting algorithms from scratch is fundamental for computer science knowledge and for scenarios requiring highly customized sorting logic. This guide will cover both the built-in methods and provide examples of implementing common algorithms like Bubble Sort and Quick Sort.

Python's Built-in Sorting

Python offers two primary ways to sort sequences: list.sort() (a method that sorts the list in-place) and sorted() (a built-in function that returns a new sorted list, leaving the original unchanged). Both can accept key and reverse arguments for customization, making them highly flexible for most use cases.

my_list = [3, 1, 4, 1, 5, 9, 2, 6]

# Using list.sort() (in-place modification)
my_list.sort()
print(f"Sorted in-place: {my_list}")

# Using sorted() (returns a new list)
new_list = sorted([5, 2, 8, 1, 9])
print(f"New sorted list: {new_list}")

# Custom sorting with key and reverse
words = ["banana", "apple", "cherry", "date"]
words.sort(key=len, reverse=True)
print(f"Sorted by length, descending: {words}")

Implementing Custom Sorting Algorithms

While built-in sorting is highly optimized, implementing algorithms like Bubble Sort, Insertion Sort, Merge Sort, or Quick Sort helps understand their underlying mechanics and computational complexity. Let's look at Bubble Sort and Quick Sort as examples to illustrate the process.

1. Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. It has a time complexity of O(n^2), making it inefficient for large datasets.

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n - i - 1):
            # Traverse the array from 0 to n-i-1
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

my_array = [64, 34, 25, 12, 22, 11, 90]
print(f"Original array: {my_array}")
bubble_sort(my_array)
print(f"Sorted array (Bubble Sort): {my_array}")

2. Quick Sort

Quick Sort is an efficient, comparison-based, divide-and-conquer sorting algorithm. It picks an element as a pivot and partitions the array around the picked pivot. The sub-arrays are then recursively sorted. Its average time complexity is O(n log n), making it significantly faster than Bubble Sort for larger datasets, though its worst-case complexity is O(n^2).

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot] # In case of duplicate pivots
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

my_array_2 = [3, 6, 8, 10, 1, 2, 1]
print(f"Original array: {my_array_2}")
sorted_array_qs = quick_sort(my_array_2)
print(f"Sorted array (Quick Sort): {sorted_array_qs}")

These examples demonstrate how to implement two distinct sorting algorithms. While Python's built-in functions are usually preferred for their optimized performance in production code, understanding and implementing these algorithms yourself provides valuable insight into computer science fundamentals, algorithm design, and problem-solving techniques.