Merge Sort

Concept

Merge Sort is an efficient, comparison-based, divide and conquer sorting algorithm. It works by recursively dividing the input array into two halves, calling itself for the two halves, and then merging the two sorted halves.

The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Characteristics

• Time Complexity:
  • Worst-case: O(n log n)
  • Average-case: O(n log n)
  • Best-case: O(n log n)
• Space Complexity: O(n) (due to the temporary arrays used for merging)
• Stability: Stable (if implemented carefully)
• Efficient for large datasets and widely used.

Code Example (C++)

#include <iostream>
#include <vector>
#include <algorithm> // For std::inplace_merge or manual merge

// Function to merge two subarrays of arr[]
// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temp arrays
    std::vector<int> L(n1), R(n2);

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

    // Merge the temp 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 there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

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

// Main function that sorts arr[left..right] using merge()
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        // Same as (left+right)/2, but avoids overflow for large left and h
        int mid = left + (right - left) / 2;

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

        merge(arr, left, mid, right);
    }
}

// Helper function to print the vector
void printVector(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};
    std::cout << "Unsorted array: ";
    printVector(data);

    mergeSort(data, 0, data.size() - 1);

    std::cout << "Sorted array: ";
    printVector(data);

    return 0;
}
// To compile and run (e.g., with g++):
// g++ your_file_name.cpp -o merge_sort_cpp
// ./merge_sort_cpp

Code Example (Python)

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Finding the mid of the array
        L = arr[:mid]      # Dividing the array elements into 2 halves
        R = arr[mid:]

        merge_sort(L)      # Sorting the first half
        merge_sort(R)      # Sorting the second half

        i = j = k = 0

        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

# Example usage:
if __name__ == "__main__":
    unsorted_array = [38, 27, 43, 3, 9, 82, 10]
    print("Unsorted array:", unsorted_array)
    # Create a copy to sort, to keep original if needed
    sorted_array = merge_sort(list(unsorted_array)) 
    print("Sorted array:", sorted_array)

    unsorted_array_2 = [12, 11, 13, 5, 6, 7]
    print("Unsorted array 2:", unsorted_array_2)
    sorted_array_2 = merge_sort(list(unsorted_array_2))
    print("Sorted array 2:", sorted_array_2)

# To run:
# python your_file_name.py