Introduction

Merge Sort is a highly efficient, stable sorting algorithm that also follows the divide-and-conquer approach to organize data. It works by recursively dividing the array into two halves until each sub-array contains a single element. Then, it merges these sub-arrays in a sorted manner to produce larger sorted arrays, eventually resulting in a fully sorted array. Merge Sort guarantees O(n log n) time complexity in all cases (worst, average, and best), making it reliable for large datasets. Although it requires additional memory for merging, it is favored for its predictable performance and stability, especially in scenarios where consistent sorting behavior is critical.

Complexity

• Best Case: O(n log n) [Occurs when the array is evenly split at every division and merged efficiently. Merge Sort always divides in half, so best case is same as average/worst.]
• Average Case: O(n log n) [Happens typically during sorting of randomly ordered data. Each split and merge still takes consistent time.]
• Worst Case: O(n log n) [Even in the worst-case scenario (e.g., reverse-sorted data), Merge Sort maintains its divide-and-conquer efficiency.]
• Space Complexity: O(n) [Due to the use of temporary arrays during the merge process. Not in-place, as additional memory is required to hold elements during merging.]

Algorithm Steps

• If the array has more than one element, split it into left and right sub-arrays.

• Apply Merge Sort recursively to the left and right sub-arrays.

• Compare elements from both sub-arrays and combine them into a single sorted array.

Example Array

[38, 27, 43, 3, 9, 82, 10]

Let’s apply Merge Sort step-by-step (dry run).

Step 1: Divide:

[38, 27, 43, 3, 9, 82, 10]
=> [38, 27, 43] and [3, 9, 82, 10]

[38, 27, 43] => [38] and [27, 43]
[27, 43] => [27] and [43]

[3, 9, 82, 10] => [3, 9] and [82, 10]
[3, 9] => [3] and [9]
[82, 10] => [82] and [10]

Now we have:

[38], [27], [43], [3], [9], [82], [10]

Step 2: Conquer (Merge and Sort):

Now start merging while sorting:

• Merge [27] and [43] → [27, 43]

• Merge [38] and [27, 43] → Compare 38 with 27 → [27, 38, 43]

• Merge [3] and [9] → [3, 9]

• Merge [82] and [10] → Compare 82 with 10 → [10, 82]

• Merge [3, 9] and [10, 82] → Compare and merge → [3, 9, 10, 82]

Step 3: Final Merge:

Merge [27, 38, 43] and [3, 9, 10, 82]

✅ Sorted Array:

[3, 9, 10, 27, 38, 43, 82]

✅ Advantages of Quick Sort:

• Consistent Time Complexity: Always runs in O(n log n) time, regardless of input order (best, average, and worst cases).
• Stable Sort: Maintains the relative order of equal elements, which is important in many applications (e.g., sorting records by multiple fields).
• Works Well with Large Datasets: Particularly efficient for linked lists and external sorting (sorting large files on disk), since it accesses data sequentially.
• Parallelizable: The divide-and-conquer nature makes it suitable for parallel execution, improving speed on multi-core systems.
• No Performance Degradation on Sorted or Reversed Data: Unlike Quick Sort, Merge Sort’s performance does not degrade with already sorted or reverse-ordered data.

❌ Disadvantages of Quick Sort:

• Higher Space Complexity: Requires O(n) extra space for temporary arrays during merging, which can be costly for large datasets or memory-limited environments.
• Not In-Place: Unlike algorithms like Quick Sort or Heap Sort, Merge Sort does not sort in-place, as it needs additional space to merge.
• Slower for Small Datasets: Due to overhead from recursive calls and extra memory allocation, it's generally slower than simpler algorithms like Insertion Sort on small arrays.
• Inefficient for Arrays in Memory: For in-memory arrays, Quick Sort often outperforms Merge Sort because of better cache usage and lower constant factors.

Code in C :

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int temp[100];  // Assumes max array size is ≤ 100
    int i = left, j = mid + 1, k = 0;

    // Merge two sorted halves into temp[]
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }

    // Copy remaining elements (if any)
    while (i <= mid)
        temp[k++] = arr[i++];
    while (j <= right)
        temp[k++] = arr[j++];

    // Copy temp[] back into arr[]
    for (i = left, k = 0; i <= right; i++, k++)
        arr[i] = temp[k];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

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

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {7, 2, 1, 6, 8, 5, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);
    printArray(arr, n);

    return 0;
}

Code in JAVA :

public class MergeSortSimple {

    // Function to merge two halves of the array
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;     // start of left half
        int j = mid + 1;  // start of right half
        int k = 0;        // index for temp

        // Merge both halves into temp[]
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // Copy remaining elements from left half
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // Copy remaining elements from right half
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // Copy sorted temp[] back to original array
        for (i = left, k = 0; i <= right; i++, k++) {
            arr[i] = temp[k];
        }
    }

    // Recursive Merge Sort function
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

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

    // Function to print the array
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // Main method
    public static void main(String[] args) {
        int[] arr = {7, 2, 1, 6, 8, 5, 3, 4};

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

Code in C++ :

#include <iostream>
using namespace std;

// Function to merge two halves of the array
void merge(int arr[], int left, int mid, int right) {
    int temp[100];  // Assumes max array size is ≤ 100
    int i = left, j = mid + 1, k = 0;

    // Merge two sorted halves into temp[]
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // Copy remaining elements (if any)
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // Copy temp[] back into arr[]
    for (i = left, k = 0; i <= right; i++, k++) {
        arr[i] = temp[k];
    }
}

// Recursive Merge Sort function
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

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

int main() {
    int arr[] = {7, 2, 1, 6, 8, 5, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);
    printArray(arr, n);

    return 0;
}

• for more topics Click Here.

Happy Coding!!