Sorting

Bubble Sort

The order of comparing i and j can be done from the front or from the back.

def bubblesort(A):
    for i in range(1, len(A)):
        for j in range(0, len(A) - 1):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]

Merge Sort

In both the best and worst cases, it's essentially a perfect $Θ(nlog⁡n)$ algorithm, and while it's typically slower than quicksort, it maintains a consistent execution speed and, most importantly, is a stable sort.

Each is continuously divided until it can no longer be split. Once the division is complete, they are sorted and then conquered.

Divide and Conquer: Divide-and-Conquer

Quick Sort

Due to its characteristic of dividing based on a pivot, it's also called the Partition-Exchange Sort. Like merge sort, it's a divide-and-conquer algorithm. Here, using the concept of a pivot, it partitions by breaking it down such that if it's smaller than the pivot, it goes to the left, and if larger, to the right.

There are various modifications and improved versions. The N.Lomuto partition is a straightforward method that always selects the rightmost pivot. In this case, the pivot is based on the rightmost value. Using this as a reference, two pointers move, and if the right pointer's value is smaller than the pivot, they swap.

def quicksort(A, low, high):
    def partition(low, high):
        pivot = A[high]
        left = low
        for right in range(low, high):
            if A[right] < pivot:
                A[left], A[right] = A[right], A[left]
                left += 1
        A[left], A[high] = A[high], A[left]
        return left
    
    if low < high:
        pivot = partition(low, high)
        quicksort(A, low, pivot - 1)
        quicksort(A, pivot + 1, high)

As its name implies, quicksort is very fast and efficient. However, in the worst-case scenario (when an already sorted array is given as input and the pivot continually ends up on the right, leading to no partitioning at all. But after $n$ rounds, it eventually compares everything), it becomes $O(n^2)$.

Unlike merge sort, which always performs consistently, quicksort has a significant performance variance based on input. However, by improving the algorithm for selecting the pivot, quicksort can be further optimized.

Stable Sort vs. Unstable Sort

A stable sorting algorithm sorts duplicate values in the same order they were input.

This preservation of input values makes stable sorting algorithms much more useful than unstable sorting algorithms. Notably, merge sort and bubble sort are stable sorts, while quicksort is unstable.

Python's default sorting algorithm uses Timsort, which heuristically combines merge sort and insertion sort.