13. Merge Sort & Quick Sort

🧸 ELI5 (Merge Sort): You have a huge pile of shuffled cards. Split the pile in half, then split those halves in half, keep splitting until each pile has just 1 card (a single card is always "sorted"). Now merge pairs of tiny sorted piles back together in order, then merge those bigger piles, until you have one giant sorted pile. Divide, then combine.

🧸 ELI5 (Quick Sort): Pick one card as the "pivot" (say, a 7). Put all smaller cards in one pile to the left, all bigger cards in a pile to the right. Now do the same trick on each smaller pile. Eventually every pile has 1 card and everything is sorted.

🌍 Real life: How you'd actually sort a huge stack of exam papers by grade if you had friends helping — split the stack among friends, each sorts their small stack, then you merge the stacks back together in order.

📝 Pseudocode (Merge Sort):

function mergeSort(list):
    if length(list) <= 1: return list
    mid = length(list) / 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

function merge(left, right):
    result = []
    while left and right are not empty:
        append smaller of left[0], right[0] to result
    append any leftovers from left or right
    return result

🐹 Go:

package main

import "fmt"

func mergeSort(list []int) []int {
	if len(list) <= 1 {
		return list
	}
	mid := len(list) / 2
	left := mergeSort(list[:mid])
	right := mergeSort(list[mid:])
	return merge(left, right)
}

func merge(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}
	result = append(result, left[i:]...)
	result = append(result, right[j:]...)
	return result
}

func main() {
	exams := []int{88, 45, 92, 67, 71, 30}
	fmt.Println(mergeSort(exams)) // [30 45 67 71 88 92]
}

🇨 C (in-place on one array, with two small malloc'd scratch buffers per merge — no garbage collector to clean up the intermediate slices Go's version allocates):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void merge(int *arr, int lo, int mid, int hi) {
    int n1 = mid - lo + 1, n2 = hi - mid;
    int *left = malloc((size_t)n1 * sizeof(int));
    int *right = malloc((size_t)n2 * sizeof(int));
    memcpy(left, arr + lo, (size_t)n1 * sizeof(int));
    memcpy(right, arr + mid + 1, (size_t)n2 * sizeof(int));

    int i = 0, j = 0, k = lo;
    while (i < n1 && j < n2) arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    while (i < n1) arr[k++] = left[i++];
    while (j < n2) arr[k++] = right[j++];

    free(left);
    free(right);
}

void merge_sort(int *arr, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(arr, lo, mid);
    merge_sort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}

int main(void) {
    int exams[] = {88, 45, 92, 67, 71, 30};
    merge_sort(exams, 0, 5);
    for (int i = 0; i < 6; i++) printf("%d ", exams[i]); // 30 45 67 71 88 92
    printf("\n");
    return 0;
}

⏱️ Complexity: Merge Sort: O(n log n) always, but needs extra space (O(n)). Quick Sort: O(n log n) average, O(n²) worst case (bad pivot choices), but sorts in place (little extra memory) — that's why it's often the default in real libraries.