Merge Sort in C++ and C

  

Merge Sort

Merge Sort is an efficient, stable, and comparison-based sorting algorithm. It follows the divide-and-conquer paradigm by recursively dividing the unsorted list into two halves, sorting each half, and then merging the sorted halves to produce the final sorted list.

What is Merge Sort?

Merge Sort is a sorting algorithm that works by dividing the input array into two halves, recursively sorting each half, and then merging the sorted halves to produce the final sorted array.

Example:

• Unsorted List: [38, 27, 43, 3, 9, 82, 10]

• Sorted List: [3, 9, 10, 27, 38, 43, 82]

Solution:

Now let’s see how to implement Merge Sort in C++ and C.

1. C++

#include <iostream>

using namespace std;

// Function to merge two subarrays

void merge(int arr[], int left, int mid, int right) {

    int n1 = mid - left + 1;

    int n2 = right - mid;

    int* leftArr = new int[n1];

    int* rightArr = new int[n2];

    // Copy data to temporary arrays

    for (int i = 0; i < n1; i++)

        leftArr[i] = arr[left + i];

    for (int j = 0; j < n2; j++)

        rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0;

    int k = left;

    // Merge the temporary arrays

    while (i < n1 && j < n2) {

        if (leftArr[i] <= rightArr[j]) {

            arr[k] = leftArr[i];

            i++;

        } else {

            arr[k] = rightArr[j];

            j++;

        }

        k++;

    }

    // Copy remaining elements of leftArr[], if any

    while (i < n1) {

        arr[k] = leftArr[i];

        i++;

        k++;

    }

    // Copy remaining elements of rightArr[], if any

    while (j < n2) {

        arr[k] = rightArr[j];

        j++;

        k++;

    }

    delete[] leftArr;

    delete[] rightArr;

}

// Function to implement Merge Sort

void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;

        // Recursively sort first and second halves

        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves

        merge(arr, left, mid, right);

    }

}

int main() {

    int arr[] = {38, 27, 43, 3, 9, 82, 10};

    int arrSize = sizeof(arr) / sizeof(arr[0]);

    cout << "Unsorted array: ";

    for (int i = 0; i < arrSize; i++)

        cout << arr[i] << " ";

    cout << endl;

    mergeSort(arr, 0, arrSize - 1);

    cout << "Sorted array: ";

    for (int i = 0; i < arrSize; i++)

        cout << arr[i] << " ";

    cout << endl;

    return 0;

}

2. C

#include <stdio.h>

#include <stdlib.h>

// Function to merge two subarrays

void merge(int arr[], int left, int mid, int right) {

    int n1 = mid - left + 1; // Size of the left subarray

    int n2 = right - mid;    // Size of the right subarray

    // Temporary arrays to hold the values of the subarrays

    int* leftArr = (int*)malloc(n1 * sizeof(int));

    int* rightArr = (int*)malloc(n2 * sizeof(int));

    // Copy data to temporary arrays leftArr[] and rightArr[]

    for (int i = 0; i < n1; i++)

        leftArr[i] = arr[left + i];

    for (int j = 0; j < n2; j++)

        rightArr[j] = arr[mid + 1 + j];

    int i = 0; // Initial index of the first subarray

    int j = 0; // Initial index of the second subarray

    int k = left; // Initial index of the merged array

    // Merge the temporary arrays back into arr[left..right]

    while (i < n1 && j < n2) {

        if (leftArr[i] <= rightArr[j]) {

            arr[k] = leftArr[i];

            i++;

        } else {

            arr[k] = rightArr[j];

            j++;

        }

        k++;

    }

    // Copy the remaining elements of leftArr[], if any

    while (i < n1) {

        arr[k] = leftArr[i];

        i++;

        k++;

    }

    // Copy the remaining elements of rightArr[], if any

    while (j < n2) {

        arr[k] = rightArr[j];

        j++;

        k++;

    }

    // Free the allocated memory

    free(leftArr);

    free(rightArr);

}

// Function to implement Merge Sort

void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2; // Find the middle point

        // Recursively sort first and second halves

        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves

        merge(arr, left, mid, right);

    }

}

int main() {

    int arr[] = {38, 27, 43, 3, 9, 82, 10};

    int arrSize = sizeof(arr) / sizeof(arr[0]);

    printf("Unsorted array: ");

    for (int i = 0; i < arrSize; i++)

        printf("%d ", arr[i]);

    printf("\n");

    mergeSort(arr, 0, arrSize - 1);

    printf("Sorted array: ");

    for (int i = 0; i < arrSize; i++)

        printf("%d ", arr[i]);

    printf("\n");

    return 0;

}

Explanation of Code:

• Merge Function: This function merges two subarrays of arr. It creates temporary arrays to hold the values of the left and right subarrays, then merges these arrays back into the original array.

• Merge Sort Function: This function recursively divides the array into two halves, sorts each half, and merges them. The base case for the recursion is when the array has one or zero elements.

• Main Function: This is the entry point of the program where the array is initialized and the mergeSort function is called.

Sample Input & Output:

Input:

• Unsorted array: [38, 27, 43, 3, 9, 82, 10]

Output:

• Sorted array: [3, 9, 10, 27, 38, 43, 82]

Conclusion:

        Merge Sort is an efficient sorting algorithm suitable for large datasets. It guarantees a time complexity of O(n log n) in all cases, making it a reliable choice for sorting operations.

**  Please do subscribe my blog for future updates and share with your friends, if you find this informative **