Sorting Algorithms Simplified

November 17, 2023 · #sorting #inertion #merge

---

1. Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm. It works by building a sorted section of the array incrementally, inserting each element into its correct position within the sorted portion.

Algorithm:

for i = 1 to n-1:
    key = array[i]
    j = i - 1
    while j >= 0 and array[j] > key:
        array[j + 1] = array[j]
        j = j - 1
    array[j + 1] = key
    

Complexity:

• Best Case: O(n) (when the array is already sorted)
• Average Case: O(n²)
• Worst Case: O(n²) (when the array is sorted in reverse order)

Space Complexity: O(1) (in-place sorting)

2. Merge Sort

Merge Sort is a divide-and-conquer algorithm. It recursively divides the array into two halves, sorts each half, and then merges the sorted halves back together.

Algorithm:

def merge_sort(array):
    if len(array) > 1:
        mid = len(array) // 2
        left = array[:mid]
        right = array[mid:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                array[k] = left[i]
                i += 1
            else:
                array[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    

Complexity:

• Best, Average, and Worst Case: O(n log n)

Space Complexity: O(n) (additional space for merging)

3. Quick Sort

Quick Sort is another divide-and-conquer algorithm. It selects a pivot element, partitions the array around the pivot such that all elements smaller than the pivot go to the left and all larger go to the right, then recursively sorts the partitions.

Algorithm:

        def quick_sort(array, low, high):
    if low < high:
        pi = partition(array, low, high)
        quick_sort(array, low, pi - 1)
        quick_sort(array, pi + 1, high)

def partition(array, low, high):
    pivot = array[high]
    i = low - 1
    for j in range(low, high):
        if array[j] < pivot:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[high] = array[high], array[i + 1]
    return i + 1
    

Complexity:

• Best Case: O(n log n) (balanced partitions)
• Average Case: O(n log n)
• Worst Case: O(n²) (if partitions are highly unbalanced)

Space Complexity: O(log n) (due to recursive stack for partitioning)

Comparison Summary

Algorithm	Best Case	Average Case	Worst Case	Space Complexity	Stable	Use Case
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Small or nearly sorted datasets
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Large datasets, external sorting
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Large datasets, fast in-memory sorting

← home