Sorting algorithms can be intimidating, but I finally took the time to break them down!

These two algorithms have long evaded me and I finally took the time to understand them. That partitioning in quick sort and magic sort in merge sort always confused me. Let’s break them down.

Quick Sort

This is a divide and conquer algorithm where we pick a pivot and partition the array around the pivot after putting pivot in its correct position. We take the left and right subarrays and repeat the process. Nothing explains it better than below video(created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania):

There are couple of strategies on how to pick the pivot choice: pick first/last as pivot, pick random element as pivot, or pick median elements as pivot.

def partition(arr, low, high):
    # Choose the pivot as the last element
    pivot = arr[high]
    
    # Pointer for greater element
    i = low - 1  

    # Traverse through all elements, comparing them with the pivot
    for j in range(low, high):
        if arr[j] < pivot:
            # If an element is smaller than the pivot, swap it with the greater element pointer
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # Swap the pivot element with the first element greater than pivot
    arr[i + 1], arr[high] = arr[high], arr[i + 1]  
    
    # Return the partition index
    return i + 1  


def quick_sort(arr, low, high):
    if low < high:
        # Find the pivot element such that elements smaller than pivot are on the left
        # and elements greater than pivot are on the right
        pivot = partition(arr, low, high)

        # Recursively apply quick sort to the left and right subarrays
        quick_sort(arr, low, pivot - 1)
        quick_sort(arr, pivot + 1, high)


# Example usage
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)

# Print the sorted array
print("Sorted array:", arr)

Output:

Sorted array: [1, 5, 7, 8, 9, 10]

But how did it come to this?

• We send the whole array to quick_sort with low = 0 and high = 5
• It checks if low < high, which is true, so it calls partition which figures out the pivot and partitions the array around it. By partition,we mean that we put all bigger values than pivot on the right and smaller values than pivot on the left.
• So now…., partition is called with whole array and low = 0 and high = 5
  • Initial array is [10, 7, 8, 9, 1, 5] and low = 0 and high = 5
  • pivot = arr[high] = arr[5] = 5
  • i = low - 1 = 0 - 1 = -1 so i is set to -1 for now
  • Now the loop runs from low to high-1, so 0 to 4
    • j = 0, arr[j] = 10, which is not less than pivot(i.e.5 ), so we don’t do anything
    • j = 1, arr[j] = 7, which is not less than pivot(i.e.5 ), so we don’t do anything
    • j = 2, arr[j] = 8, which is not less than pivot(i.e. 5), so we don’t do anything
    • j = 3, arr[j] = 9, which is not less than pivot(i.e. 5), so we don’t do anything
    • j = 4, arr[j] = 1, which is less than pivot, so we increment i by 1(becomes 0) and swap arr[i] and arr[j], so now i = 0 and arr becomes [1, 7, 8, 9, 10], This is the important step worth understanding.
  • After the loop, state is i = 0 and arr = [1, 7, 8, 9, 10, 5]
  • We swap i+1 and high, so arr becomes [1, 5, 8, 9, 10, 7]
  • We return i+1 which is 1. So now notice, all numbers that are smaller than 5 are on the left and all numbers that are bigger than 5 are on the right. Pivot that’s returned is 1, which is the index of 5.
• pivot recieves 1, and array as [1, 5, 8, 9, 10, 7]. Now we call quick_sort on left and right subarrays. This is the next most important step.
• We keep recursively calling quick_sort on left and right subarrays until we reach the base case where low >= high.

Time Complexity:

• Best Case => T(n) = 2T(n/2) + O(n) => O(nlogn)
• Worst Case => T(n) = T(n-1) + O(n) => O(n^2)
• Average Case => O(nlogn)

Merge Sort

This is another divide and conquer algorithm where we divide the array into two halves, sort them recursively and then merge them. Another great video from same group I believe that explains it well is below:

There is no pivot involved, we just divide the array into two halves, recursively call merge sort and merge them later.

# Dictionary to track arrays at each recursion level
levels = {}

def merge_sort(arr, level):
    """
    Recursively splits the array into halves and tracks the levels.
    Merges the sorted halves back together.
    """
    
    # Store the current level arrays for visualization
    if level not in levels:
        levels[level] = []  # Initialize the list for this level
        
    levels[level].append(arr.copy())  # Store a copy to avoid modification issues
    
    # Base case: If the array has one or no elements, it's already sorted
    if len(arr) > 1:
        mid = len(arr) // 2  # Find the middle index

        # Split array into two halves
        left_half = arr[:mid]
        right_half = arr[mid:]

        # Recursively apply merge sort on both halves
        merge_sort(left_half, level + 1)
        merge_sort(right_half, level + 1)

        # Merge the sorted halves
        merge(arr, left_half, right_half)

def merge(arr, left_half, right_half):
    """
    Merges two sorted subarrays (left_half and right_half) into arr.
    """
    i = j = k = 0  # Initialize indices for left_half, right_half, and merged array

    # Compare elements from both halves and merge in sorted order
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            arr[k] = left_half[i]
            i += 1
        else:
            arr[k] = right_half[j]
            j += 1
        k += 1

    # Copy any remaining elements from left_half
    while i < len(left_half):
        arr[k] = left_half[i]
        i += 1
        k += 1

    # Copy any remaining elements from right_half
    while j < len(right_half):
        arr[k] = right_half[j]
        j += 1
        k += 1

# Example array
arr = [10, 7, 8, 9, 1, 5]

# Perform merge sort, tracking levels
merge_sort(arr, 0)

# Print how the array is divided at each level
for level in levels:
    print("Level:", level, ", Arrays:", levels[level])

# Print the final sorted array
print("Final Sorted Array:", arr)

Output:

Level: 0 , Arrays: [[1, 5, 7, 8, 9, 10]]
Level: 1 , Arrays: [[7, 8, 10], [1, 5, 9]]
Level: 2 , Arrays: [[10], [7, 8], [9], [1, 5]]
Level: 3 , Arrays: [[7], [8], [1], [5]]
Final Sorted Array: [1, 5, 7, 8, 9, 10]

But how did it come to this?

• We send the whole array to merge_sort with level = 0
• Notice that I print the array even before checking if length is > 1. This is because I want to see the state of array at each level.
• I store the state of array at each level in a dictionary called levels.
• Now checking if length of array is > 1, which is true, so we calculate mid and divide the array into two halves. If it’s not greater than, why sort as it’s trivially sorted as there is only 1 element.
• We recursively call merge_sort on left and right halves, incrementing level by 1.
  • This is the most important step, we keep recursively calling merge_sort on left and right halves until we reach the base case where length of array is 1 where it gets returned and we start merging.
  • But where does the sorting happen?
  • Sorting happens in merge function.
• We merge the two halves using merge function.
  • Base case with just 1 element let’s say for [7] and [8] which were called by merge_sort on left and right halves respectively at an upper level. Then when [7],[8] are returned and then merge is called, it compares 7 and 8 and puts them in correct order in arr.
  • Another example would be merging of [7,8,10], [1,5,9] which were called by merge_sort on left and right halves respectively at an upper level. Then when [7,8,10],[1,5,9] are returned and then merge is called, it compares 7 and 1, then puts 1 first, then compares 7 with 5 and puts 5 after 1, then compares 7 with 9 and this time puts 7 after 5, it continues and puts them in correct order in arr.

Time Complexity:

Worst Case: T(n) = 2*T(n/2) + O(n) -> O(n log n)

Comparison of Quick Sort and Merge Sort

Both Quick Sort and Merge Sort are efficient sorting algorithms, but they have different characteristics and use cases. Here’s a comparison of the two:

References

• GeeksForGeeks: QuickSort
• GeeksForGeeks: MergeSort
• QuickSort Folk Dance
• MergeSort Folk Dance