Merge Sort Algorithm

What is Merge Sort?

Merge Sort is a divide-and-conquer sorting algorithm. It works by dividing the array into two halves, sorting each half independently, and then merging the sorted halves back together. The merging process ensures that the combined array is sorted. Merge Sort is a stable and efficient sorting algorithm that performs well even on large datasets.

How Merge Sort Works

Merge Sort follows a recursive approach by dividing the input array into smaller subarrays, sorting them, and then merging them back together. The divide-and-conquer strategy works as follows:

Step-by-step explanation:

  1. Divide: The array is recursively divided into two equal halves until each subarray contains only one element (a single element is trivially sorted).
  2. Conquer: Each subarray is then merged with another sorted subarray to form a sorted larger array.
  3. Combine: The process continues recursively until all the subarrays are merged back into a single sorted array.

Example of Merge Sort

Let’s take an example of sorting the array [12, 11, 13, 5, 6, 7]:

  1. Initial List: [12, 11, 13, 5, 6, 7]
  2. First Step (Divide):
    • Split into two halves: [12, 11, 13] and [5, 6, 7].
  3. Second Step (Divide):
    • Split [12, 11, 13] into [12] and [11, 13].
    • Split [11, 13] into [11] and [13].
    • Split [5, 6, 7] into [5] and [6, 7].
    • Split [6, 7] into [6] and [7].
  4. Third Step (Merge):
    • Merge [11] and [13] into [11, 13].
    • Merge [12] and [11, 13] into [11, 12, 13].
    • Merge [6] and [7] into [6, 7].
    • Merge [5] and [6, 7] into [5, 6, 7].
  5. Final Step (Combine):
    • Merge [11, 12, 13] and [5, 6, 7] into [5, 6, 7, 11, 12, 13].

The array is now sorted.

C++ Program to implement Merge Sort Algorithm

cpp
#include <iostream>
using namespace std;

// Function to merge two halves of the array
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

    // Temporary arrays
    int leftArr[n1], rightArr[n2];

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

    // Initial indices for subarrays
    int i = 0, j = 0, k = left;

    // Merge the temp 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++;
    }
}

// Function to perform merge sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // Calculate 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);
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Main function
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    cout << "Sorted array: ";
    printArray(arr, arr_size);

    return 0;
}

Java Program to implement Merge Sort Algorithm

java
public class Main {
    // Function to merge two halves of the array
    public static 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

        // Temporary arrays
        int leftArr[] = new int[n1];
        int rightArr[] = new int[n2];

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

        // Initial indices for subarrays
        int i = 0, j = 0, k = left;

        // Merge the temp 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++;
        }
    }

    // Function to perform merge sort
    public static void mergeSort(int arr[], int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2; // Calculate 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);
        }
    }

    // Function to print the array
    public static void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // Main function
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};

        System.out.println("Original array:");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Python Program to implement Merge Sort Algorithm

python
# Function to merge two halves of the array
def merge(arr, left, mid, right):
    # Create temporary arrays for left and right subarrays
    leftArr = arr[left:mid+1]
    rightArr = arr[mid+1:right+1]

    # Initial indexes for left, right, and merged subarrays
    i = j = 0
    k = left

    # Merge the temp arrays back into arr[left..right]
    while i < len(leftArr) and j < len(rightArr):
        if leftArr[i] <= rightArr[j]:
            arr[k] = leftArr[i]
            i += 1
        else:
            arr[k] = rightArr[j]
            j += 1
        k += 1

    # Copy the remaining elements of leftArr[], if any
    while i < len(leftArr):
        arr[k] = leftArr[i]
        i += 1
        k += 1

    # Copy the remaining elements of rightArr[], if any
    while j < len(rightArr):
        arr[k] = rightArr[j]
        j += 1
        k += 1

# Function to perform merge sort
def merge_sort(arr, left, right):
    if left < right:
        mid = (left + right) // 2  # Calculate the middle point

        # Recursively sort first and second halves
        merge_sort(arr, left, mid)
        merge_sort(arr, mid + 1, right)

        # Merge the sorted halves
        merge(arr, left, mid, right)

# Function to print the array
def print_array(arr):
    print(" ".join(map(str, arr)))

# Main function
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7]

    print("Original array:")
    print_array(arr)

    merge_sort(arr, 0, len(arr) - 1)

    print("Sorted array:")
    print_array(arr)

How the Merge Sort Works:

  1. Split: The array is divided into two subarrays until each subarray contains a single element. This division happens recursively, halving the array at each level.
  2. Merge: Once the array is split into individual elements, the algorithm begins merging them back together in sorted order.

Each of these implementations illustrates how to apply Merge Sort by splitting the array into two parts, sorting each part, and then merging the two sorted parts back together.

Properties of Merge Sort

  • Time Complexity:
    • Best Case: O(n log n)
    • Average Case: O(n log n)
    • Worst Case: O(n log n)
  • Space Complexity: O(n) - Merge Sort requires additional space for the temporary arrays used during merging.
  • Stability: Merge Sort is a stable sorting algorithm, meaning it maintains the relative order of equal elements.
  • Adaptability: Merge Sort is not adaptive. It always has a time complexity of O(n log n), regardless of whether the input is already sorted.

When to Use Merge Sort ?

Merge Sort is particularly useful for large datasets or datasets that require stable sorting. Due to its O(n log n) time complexity, it outperforms algorithms like Insertion Sort or Selection Sort for large arrays. However, its additional space requirement makes it less efficient for memory-constrained environments.

DSA

5387

569

Related Articles