Merge sort command line demo

mergesort.c

/*
 * Merge sort implementation for study purposes
 *
 * Dec 19, 2024
 * 
 * Alex McColm
 * [email protected]
*/
#include <stdio.h>
#include <stdlib.h>

// ============================================================================
// ========================== Merge & merge sort ==============================
// ============================================================================

/*
 * Merges a subarray inside `arr`.
 * The left array goes from l1 up to, but not including, the midpoint.
 * The right array goes from the midpoint to r1.
 * The merged array stretches from l1 to r2.
 */
void merge(int arr[], int n, int l1, int mid, int r2) {
    int i = 0; // Array 1 == L1:mid counter
    int j = 0; // Array 2 == mid:r2 counter
    int k = 0; // Merged  == l1:r2  counter

    // We'll use a copy of the array's original state for all compares
    int * copy = calloc(n, sizeof(int));
    
    for (int m = 0; m < n; m++)
        copy[m] = arr[m];

    // While there are elements from both...
    while ( (i < mid - l1) && (j < r2 - mid) ) {
        // Add element from arr1 if <=
        if (copy[i + l1] <= copy[j + mid]) {
            arr[l1 + k] = copy[i + l1];
            i++;
        } else {
        // Else add element from arr2
            arr[l1 + k] = copy[j + mid];
            j++;
        }
        k++;
    }

    // Copy any remaining elements
    while (i < mid - l1) {
        arr[l1 + k] = copy[i + l1];
        i++;
        k++;
    }

    while (j < r2 - mid) {
        arr[l1 + k] = copy[j + mid];
        j++;
        k++;
    }

    // We are done with the memory for the array copy
    free(copy);
}

/*
 * Recursively sorts the subarray of `arr`, an array of total
 * length `n`, that runs from `left` to `right`, by dividing
 * the subarray into two, and merging the two in order, down to
 * arrays of length 2, where the "swaps" happen in a sense, 
 * and length 1, which are sorted.
 */
void merge_sort(int arr[], int n, int left, int right) {
        
    if (left >= right) {
        return;
    }
    
    // Base case: length < 2
    if (right - left <= 1) {
        return;
    }

    // Detr. midpoint, then merge_sort both halves
    int mid = left + (right - left) / 2;

    merge_sort(arr, n, left, mid);
    merge_sort(arr, n, mid, right);

    // Now merge the halves
    merge(arr, n, left, mid, right);
}

// ============================================================================
// ===================== Driver code & helper functions =======================
// ============================================================================

/*
 * Prints an array of ints to stdout separated by commas.
 */
void print_arr(int arr[], int n) {
    for (int i = 0; i < n - 1; i++)
        printf("%d, ", arr[i]);
    printf("%d\n", arr[n - 1]);
}

/*
 * Collects a list of ints from the remainder of the arguments vector.
 * Assumes there is nothing in the arguments but the binary name and
 * a series of integers.
 * Allocates memory. Caller's responsibility to free.
 */
int* ints_from_args(int n, char **argv) {
    int * array = calloc(n, sizeof(int));
    
    for (int i = 1; i <= n; i++) {
        array[i - 1] = atoi(argv[i]);
    }
    
    return array;
}

int main(int argc, char **argv) {

    // Exit if arguments not given.
    if (argc < 2) {
        fprintf(stderr, "Run with 1+ integers as arguments.\n");
        exit(1);
    }

    // Collect list of integers from arguments.
    int n = argc - 1;

    int * array = ints_from_args(n, argv);

    // Sort and print result
    merge_sort(array, n, 0, n);

    print_arr(array, n);

    // Clean up and exit.
    free(array);

    return 0;
}