C Program For Merge Sort Taking Input From User

This article will guide you through implementing the Merge Sort algorithm in C, demonstrating how to take an array of integers as input from the user and sort it efficiently. You will learn the fundamental divide-and-conquer strategy behind Merge Sort and how to write the necessary C functions.

Problem Statement

Sorting a list of numbers is a fundamental task in computer science. While many sorting algorithms exist, some, like Selection Sort or Bubble Sort, become inefficient for large datasets due to their O(n^2) time complexity. The problem is to efficiently sort an array of integers, especially for larger inputs, using an algorithm that offers better performance.

Example

Consider an unsorted array of numbers: [38, 27, 43, 3, 9, 82, 10]

After applying Merge Sort, the array will be sorted in ascending order: [3, 9, 10, 27, 38, 43, 82]

Background & Knowledge Prerequisites

To understand this article, you should have a basic understanding of:

• C Programming Fundamentals: Variables, data types, arrays, loops (for, while).
• Functions: Defining and calling functions, passing arguments.
• Pointers: Basic understanding of how pointers work with arrays.
• Recursion: The concept of a function calling itself.

No specific library setup beyond the standard C compiler is required. We will primarily use stdio.h for input/output.

Use Cases or Case Studies

Merge Sort is a powerful algorithm applicable in various scenarios:

• External Sorting: When data to be sorted is too large to fit into memory, Merge Sort can efficiently sort chunks of data, then merge the sorted chunks.
• Data Processing: Widely used in database management systems and data warehouses for sorting records before analysis or indexing.
• Parallel Computing: Its divide-and-conquer nature makes it suitable for parallel implementations, where different parts of the array can be sorted concurrently.
• Algorithm Foundations: Forms the basis for other algorithms like external sort and is often a component in more complex data structures and algorithms.
• Stable Sorting: Merge Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements. This property is crucial in scenarios where original order matters for identical values.

Solution Approaches

Merge Sort operates on the "divide and conquer" principle. It recursively divides the array into two halves until it reaches individual elements (which are inherently sorted). Then, it merges these sorted subarrays back together to produce a fully sorted array.

Approach 1: The merge Function (Conquer Step)

This function is the core of Merge Sort. It takes two sorted subarrays and merges them into a single sorted array.

• Summary: Combines two already sorted subarrays into one larger sorted array.
• Code Snippet:

// Function to merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge the temp arrays back into arr[left..right]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = left; // Initial index of merged subarray

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

    // Copy the remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Run

• Stepwise Explanation:

1. Calculate Sizes: Determine the sizes of the two subarrays (n1 for left, n2 for right).
2. Create Temp Arrays: Two temporary arrays, L and R, are created to hold the elements of the left and right subarrays, respectively.
3. Copy Data: Elements from the original arr are copied into L and R.
4. Merge Back: Using three pointers (i for L, j for R, k for arr), elements are compared from L and R. The smaller element is placed into the correct position in the original arr, and its respective pointer (i or j) and the merged array pointer (k) are incremented.
5. Copy Remaining: After one of the temporary arrays is exhausted, any remaining elements from the other temporary array are copied directly into arr.

Approach 2: The mergeSort Function (Divide Step)

This recursive function divides the array into two halves and calls itself for each half, eventually calling the merge function to combine them.

• Summary: Recursively divides the array into halves until single elements remain, then calls merge to combine them in sorted order.
• Code Snippet:

// Function to implement Merge Sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // Find the middle point
        int mid = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

Run

• Stepwise Explanation:

1. Base Case: The recursion stops when left is not less than right, meaning the subarray has one or zero elements (which are already sorted).
2. Find Midpoint: Calculates the middle index of the current subarray. The left + (right - left) / 2 approach prevents potential overflow compared to (left + right) / 2 for very large left and right values.
3. Recursive Calls: mergeSort is called recursively for the left half (left to mid) and the right half (mid + 1 to right).
4. Merge Halves: Once the recursive calls return (meaning the subarrays are sorted), the merge function is called to combine them into a single sorted subarray.

Putting It All Together: Complete C Program with User Input

This integrates the merge and mergeSort functions into a complete program that prompts the user for the array size and elements, sorts them, and prints the result.

• Summary: A complete C program that takes user input for an array, sorts it using Merge Sort, and displays the sorted array.
• Full Code Example:

// Merge Sort with User Input
#include <stdio.h>
#include <stdlib.h> // For malloc and free

// Function to merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    // Copy data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge the temp arrays back into arr[left..right]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = left; // Initial index of merged subarray

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

    // Copy the remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    // Free the dynamically allocated temporary arrays
    free(L);
    free(R);
}

// Function to implement Merge Sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // Find the middle point
        int mid = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    // Step 1: Declare variables for array size and pointer
    int size;
    int *arr;

    // Step 2: Get array size from user
    printf("Enter the number of elements: ");
    scanf("%d", &size);

    // Step 3: Dynamically allocate memory for the array
    arr = (int *)malloc(size * sizeof(int));
    if (arr == NULL) {
        printf("Memory allocation failed!\\n");
        return 1; // Indicate an error
    }

    // Step 4: Get array elements from user
    printf("Enter %d integers:\\n", size);
    for (int i = 0; i < size; i++) {
        printf("Element %d: ", i + 1);
        scanf("%d", &arr[i]);
    }

    // Step 5: Print the original array
    printf("Original array: ");
    printArray(arr, size);

    // Step 6: Call mergeSort to sort the array
    mergeSort(arr, 0, size - 1);

    // Step 7: Print the sorted array
    printf("Sorted array: ");
    printArray(arr, size);

    // Step 8: Free the dynamically allocated memory
    free(arr);

    return 0;
}

Run

• Sample Output:

Enter the number of elements: 7
Enter 7 integers:
Element 1: 38
Element 2: 27
Element 3: 43
Element 4: 3
Element 5: 9
Element 6: 82
Element 7: 10
Original array: 38 27 43 3 9 82 10 
Sorted array: 3 9 10 27 38 43 82

• Stepwise Explanation for main function:

1. Declare Variables: size stores the number of elements, and arr is a pointer that will point to the dynamically allocated array.
2. Get Size: Prompts the user to enter the desired array size.
3. Allocate Memory: malloc is used to dynamically allocate memory for the array based on the user-provided size. Error handling checks if allocation was successful.
4. Get Elements: A loop prompts the user to enter each integer element, storing it in the allocated array.
5. Print Original: The printArray helper function displays the unsorted input array.
6. Call Merge Sort: The mergeSort function is called with the array, the starting index 0, and the ending index size - 1.
7. Print Sorted: After mergeSort completes, printArray is called again to display the now-sorted array.
8. Free Memory: free(arr) is crucial to release the dynamically allocated memory back to the system, preventing memory leaks.

Conclusion

Merge Sort is an efficient, comparison-based sorting algorithm with a time complexity of O(n log n) in all cases (best, average, worst). It's a stable sort and well-suited for large datasets and external sorting. By understanding its divide-and-conquer strategy and implementing the merge and mergeSort functions, you can effectively sort arrays in C.

Summary

• Merge Sort is a divide-and-conquer algorithm for sorting.
• It breaks down an array into smaller subarrays until each subarray contains only one element.
• The mergeSort function handles the recursive division.
• The merge function combines two sorted subarrays into a single sorted array.
• Time complexity is O(n log n), making it efficient for large inputs.
• Requires O(n) auxiliary space for temporary arrays during the merge operation.
• The complete C program demonstrates user input, dynamic memory allocation, and the application of Merge Sort.