Merge Sort as Divide and Conquer in DSA C - Build from Scratch

Merge Sort as Divide and Conquer

📖 Scenario: You have a list of numbers that you want to sort from smallest to largest. Sorting helps you find things faster, like organizing books by their titles on a shelf.

🎯 Goal: You will build a program that sorts a list of numbers using the merge sort method. Merge sort splits the list into smaller parts, sorts those parts, and then joins them back together in order.

📋 What You'll Learn

Create an array with exact numbers

Create a variable for the array size

Write a function to merge two sorted parts

Write a function to split and sort the array using merge sort

Print the sorted array

💡 Why This Matters

🌍 Real World

Sorting is used everywhere, like organizing files, searching data quickly, and arranging items in online stores.

💼 Career

Understanding merge sort helps in software development, data analysis, and any job that requires efficient data handling.

1

Create the initial array

Create an integer array called arr with these exact values: 38, 27, 43, 3, 9, 82, 10. Also create an integer variable called n and set it to the size of arr.

DSA C

int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
// Your code here

Hint

Use int arr[] = {38, 27, 43, 3, 9, 82, 10}; to create the array and int n = sizeof(arr) / sizeof(arr[0]); to get its size.

2

Write the merge function

Write a function called merge that takes the array arr, and three integers l, m, and r. This function will merge two sorted parts of the array: from l to m and from m+1 to r. Use temporary arrays to help merge in sorted order.

DSA C

int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);

void merge(int arr[], int l, int m, int r) {
    // Your code here
}

Hint

Use two temporary arrays to hold the left and right parts. Then compare elements and copy the smaller one back to arr.

3

Write the mergeSort function

Write a function called mergeSort that takes the array arr, and two integers l and r. This function will split the array into halves, call itself recursively to sort each half, and then call merge to join the halves in order.

DSA C

int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    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];

    int i = 0, j = 0, k = l;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    // Your code here
}

Hint

Split the array by finding the middle index. Call mergeSort on left and right halves, then merge them.

4

Print the sorted array

Call mergeSort on the array arr with l = 0 and r = n - 1. Then use a for loop with variable i from 0 to n - 1 to print each element of arr separated by a space.

DSA C

Hint

Call mergeSort(arr, 0, n - 1); to sort. Then print each element with a space using a for loop.