Recursion and Sorting III #

Towers of Hanoi #

You have 3 pegs: Source (A), Auxiliary (B), Destination (C)
n disks of different sizes are stacked on Source peg
Goal: Move all disks to Destination peg
Rules:
1. Only one disk moved at a time
2. A disk can only be placed on an empty peg or on a larger disk
3. Disks must maintain order

Recursive Idea #

To move n disks from A → C using B:

Move n-1 disks from A → B (using C)
Move the largest disk from A → C
Move n-1 disks from B → C (using A)

Example for 3 Disks #

Move 2 disks from A → B
Move disk 3 from A → C
Move 2 disks from B → C

Moves: A → C A → B C → B A → C B → A B → C A → C

C Implementation #

#include <stdio.h>

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);
}

Pythontutor

What is Merge Sort? #

A Divide and Conquer sorting algorithm
Steps:
1. Divide array into two halves
2. Recursively sort both halves
3. Merge the two sorted halves
Always O(n log n) time complexity

Algorithm Outline #

If array has 0 or 1 elements → already sorted
Otherwise:
- Divide array into left and right halves
- Recursively sort each half
- Merge two sorted halves into one sorted array

Merge Function #

// merges the subarrays from indices l to m and m+1 to r
// assumes that the subarrays are sorted
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1; // length of first subarray 
    int n2 = r - m; // length of second subarray

    // create new arrays for the subarrays and copy data there
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    // compare the current index elements of L, R and 
    // insert the smaller into the orginal array 'arr'
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    // once one of the subarray is exhausted, copy remaining
    // elements from the other subarray to the orginal array
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

Merge Sort Function #

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        // Recursively sort left and right halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // Merge sorted halves
        merge(arr, l, m, r);
    }
}

Example Dry Run Array = {12, 11, 13, 5, 6, 7}

Divide → {12, 11, 13} and {5, 6, 7}

Recursively sort:

{12, 11, 13} → {11, 12, 13}

{5, 6, 7} → {5, 6, 7}

Merge:

{11, 12, 13} and {5, 6, 7} → {5, 6, 7, 11, 12, 13}

Visualization of Recursive Calls #

mergeSort([12,11,13,5,6,7])
 → mergeSort([12,11,13])
     → mergeSort([12,11])
        → mergeSort([12]) & mergeSort([11])
        → merge([12], [11]) → [11,12]
     → mergeSort([13]) → [13]
     → merge([11,12], [13]) → [11,12,13]
 → mergeSort([5,6,7]) → [5,6,7]
 → merge([11,12,13], [5,6,7]) → [5,6,7,11,12,13]