C++ Program Of Simple Merge Sort Implementation Using Array In Ascending Order

Merge sort is an efficient, comparison-based sorting algorithm. It works on the principle of divide and conquer, recursively breaking down an array into smaller subarrays until each subarray contains only one element, then merging those subarrays back together in a sorted manner. In this article, you will learn how to implement a simple merge sort program using arrays in C++ to sort elements in ascending order.

Problem Statement

Efficiently arranging a collection of data in a specific order is a fundamental task in computer science. Unsorted data can lead to slow search times and inefficient processing in many applications. The challenge is to sort an array of integers into ascending order using a robust and performant algorithm like Merge Sort.

Example

Consider an unsorted array: [12, 11, 13, 5, 6, 7]

After applying merge sort, the array will be sorted in ascending order as: [5, 6, 7, 11, 12, 13]

Background & Knowledge Prerequisites

To understand and implement merge sort, you should be familiar with the following C++ concepts:

• Arrays: Basic understanding of declaring, initializing, and accessing array elements.
• Functions: How to define and call functions, including passing arrays.
• Recursion: The concept of a function calling itself. Merge sort is inherently recursive.
• Pointers (optional but helpful): While not strictly required for this array-based implementation, a basic grasp of pointers helps in understanding array manipulation.

Use Cases or Case Studies

Merge sort is a versatile algorithm used in various applications due to its stability and guaranteed time complexity.

• External Sorting: When data is too large to fit into memory, merge sort can efficiently sort data stored on disk.
• Inversion Count Problem: It can be modified to count the number of inversions in an array efficiently.
• Parallel Sorting: Merge sort's divide-and-conquer nature makes it suitable for parallel implementations, speeding up sorting on multi-core processors.
• Linked Lists: Unlike Quick Sort, Merge Sort is particularly efficient for sorting linked lists because it doesn't require random access to elements.
• Data Validation and Deduplication: Sorting allows for easier identification of duplicate entries or anomalies in large datasets.

Solution Approaches

Merge sort primarily consists of two main functions: mergeSort (the recursive function that divides the array) and merge (the function that combines sorted subarrays).

Implementing the merge function

The merge function is the core of the merge sort algorithm. It takes two sorted subarrays and combines them into a single sorted array.

• One-line summary: Combines two already sorted subarrays into one larger sorted array.

// Merge Sort Implementation
#include <iostream>
#include <vector> // Using vector for dynamic array in main, but merge sort works with raw arrays too.

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

    // Create temporary arrays
    int* L = new int[n1];
    int* R = new int[n2];

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

    // Merge the temporary arrays back into arr[left..right]
    int i = 0; // Initial index of first subarray
    int j = 0; // Initial index of second subarray
    int 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 memory
    delete[] L;
    delete[] R;
}

// Placeholder for main function to demonstrate calling merge conceptually
// int main() {
//     int arr[] = {3, 5, 2, 4}; // Example: merge([3,5], 0, 0, 1) and ([2,4], 2, 2, 3)
//     // After sorting subarrays: [3,5] and [2,4]
//     // Call merge(arr, 0, 1, 3) where arr currently is {3,5,2,4}
//     // Expected output of merge would transform arr to {2,3,4,5}
//     return 0;
// }

Run

• Stepwise explanation:

1. Calculate Subarray Sizes: n1 is the size of the left subarray (arr[left...mid]) and n2 is the size of the right subarray (arr[mid+1...right]).
2. Create Temporary 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 array 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 arr at index k, and its respective pointer (i or j) is incremented. The k pointer is always incremented.
5. Copy Remaining Elements: If one of the temporary arrays runs out of elements, the remaining elements from the other array are simply copied directly into arr.
6. Deallocate Memory: The dynamically allocated temporary arrays L and R are deleted to prevent memory leaks.

Implementing the mergeSort function

The mergeSort function is the recursive part that divides the array.

• One-line summary: Recursively divides the array into two halves until single elements remain, then calls the merge function to combine them.

// Merge Sort Implementation
#include <iostream>
#include <vector> // Using vector for dynamic array

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

    int* L = new int[n1];
    int* R = new int[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0;
    int j = 0;
    int k = left;

    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++;
    }

    delete[] L;
    delete[] R;
}

// Main function that implements 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);
    }
}

// Utility function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

int main() {
    // Step 1: Initialize an array
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Print the original array
    std::cout << "Original array: ";
    printArray(arr, arr_size);

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

    // Step 4: Print the sorted array
    std::cout << "Sorted array: ";
    printArray(arr, arr_size);

    return 0;
}

Run

• Sample output:

  Original array: 12 11 13 5 6 7 
  Sorted array: 5 6 7 11 12 13

• Stepwise explanation:

1. Base Case: The recursion stops when left is greater than or equal to right, meaning the subarray has one or zero elements, which is considered sorted.
2. Find Midpoint: Calculates the middle index mid to divide the array into two halves. Using left + (right - left) / 2 avoids potential integer overflow compared to (left + right) / 2 for very large left and right values.
3. Recursive Calls:

• mergeSort(arr, left, mid) recursively sorts the left half.
• mergeSort(arr, mid + 1, right) recursively sorts the right half.

1. Merge: After the two halves are sorted by the recursive calls, the merge(arr, left, mid, right) function is called to combine these sorted halves into a single sorted subarray.

Conclusion

Merge sort stands out as a robust sorting algorithm due to its stable performance characteristics. With a time complexity of O(n log n) in all cases (best, average, and worst), it offers predictable efficiency, making it a reliable choice for various sorting tasks, especially with large datasets or when stability is critical. Its clear divide-and-conquer strategy makes it an excellent algorithm to understand fundamental computer science principles.

Summary

• Merge sort is a divide and conquer algorithm.
• It works by recursively splitting an array into halves until individual elements are reached.
• The merge function combines two sorted subarrays into a single sorted array.
• The mergeSort function handles the recursive splitting and calls merge.
• Its time complexity is O(n log n) in all cases (best, average, worst).
• Merge sort is a stable sorting algorithm, meaning elements with equal values maintain their relative order.
• It often requires O(n) auxiliary space for temporary arrays in typical implementations.