Merge Sort

Merge Sort

Description: Merge sort is a classic divide-and-conquer sorting algorithm that splits an array into two halves, recursively sorts each half, and then merges the sorted halves back together. This approach ensures that the entire array is sorted in a systematic way.

How It Works

1. Divide: If the array has more than one element, split it into two halves.
2. Conquer: Recursively sort both halves.
3. Combine: Merge the two sorted halves into a single sorted array.

Time Complexity

• Worst Case: $O(n \log n)$
• Average Case: $O(n \log n)$
• Best Case: $O(n \log n)$ — merge sort always divides the array and merges, regardless of the initial order of elements.

Space Complexity

• Space Complexity: $O(n)$ — merge sort requires additional space for the temporary arrays used during the merging process.

Stability

• Stability: Merge sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements.

Example Code

Here's a C++ implementation of merge sort:

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // Size of left subarray
    int n2 = right - mid;    // Size of right subarray

    int* L = new int[n1]; // Create left subarray
    int* R = new int[n2]; // Create right subarray

    // Copy data to temp 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];

    int i = 0; // Initial index of first subarray
    int j = 0; // Initial index of second subarray
    int k = left; // Initial index of merged subarray

    // Merge the temp arrays back into arr[left..right]
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

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

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

    delete[] L; // Free the temporary arrays
    delete[] R;
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // Prevent overflow
        mergeSort(arr, left, mid); // Sort first half
        mergeSort(arr, mid + 1, right); // Sort second half
        merge(arr, left, mid, right); // Merge the sorted halves
    }
}

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

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Explanation of the Code

1. Function Definitions:

   • merge: Merges two sorted subarrays into a single sorted array.
   • mergeSort: Recursively sorts the array by dividing it into two halves.

2. Merging Process:

   • The merge function first calculates the sizes of the two subarrays and creates temporary arrays to hold the values.
   • It then copies the elements into these temporary arrays, compares the elements from both arrays, and merges them back into the original array.

3. Recursive Sort:

   • The mergeSort function recursively splits the array until it reaches base cases (single-element arrays).
   • After sorting both halves, it calls the merge function to combine them back into a sorted array.

4. Output: Finally, the program prints the sorted array.

Conclusion

Merge sort is an efficient and stable sorting algorithm, particularly suitable for large datasets. Its $O(n \log n)$ time complexity makes it faster than simpler algorithms like bubble sort and insertion sort for larger lists. However, its requirement for additional memory can be a downside in memory-constrained environments. Merge sort is often used in situations where stability is important, such as in external sorting scenarios where data does not fit into memory.