Merge Sort | CrackEase

Merge Sort

Merge Sort is a classic divide-and-conquer sorting algorithm. It splits the array into halves recursively until each sub-array has one element, and then merges those sub-arrays back together in sorted order.

Execution of Merge sort

Dividing

The algorithm divides the array repeatedly into two halves until each sub-array contains a single element. This is the "divide" step of divide and conquer.

Conquering / Merging

The sub-arrays are then merged pairwise to produce sorted sub-arrays. Each merge step produces a larger sorted array until the whole array is merged and sorted.

Code

  
#include <stdio.h>
#include <stdlib.h>

void mergeSort(int[], int, int); 
void merge(int[], int, int, int);

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

int main(void) 
{
    int a[10] = {11, 9, 6, 19, 33, 64, 15, 75, 67, 88};
    int size = sizeof(a) / sizeof(a[0]);

    printf("Before Sorting : ");
    display(a, size);

    mergeSort(a, 0, size - 1);

    printf("After Sorting : ");
    display(a, size);

    return 0;
}

void mergeSort(int a[], int left, int right)
{
    int mid;
    if (left < right)
    {
        // use mid = left + (right - left) / 2 to avoid overflow on very large indexes
        mid = left + (right - left) / 2;

        // recursively sort first and second halves
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // temporary arrays
    int *L = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));

    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0; j = 0; k = left;

    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
}

  
#include <iostream>
using namespace std;

void mergeSort(int[], int, int);
void merge(int[], int, int, int);

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() 
{
    int array[] = {11, 9, 6, 19, 33, 64, 15, 75, 67, 88};
    int size = sizeof(array) / sizeof(array[0]);

    cout << "Before Sorting : ";
    printArray(array, size);

    mergeSort(array, 0, size - 1);

    cout << "After Sorting : ";
    printArray(array, size);

    return 0;
}

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

        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // temporary arrays
    int *L = new int[n1];
    int *R = new int[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0; j = 0; k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    delete[] L;
    delete[] R;
}

  
// Java Program for Merge Sort
class Main {
    public static void display(int[] arr, int size) {
        for (int i = 0; i < size; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] a = {11, 9, 6, 19, 33, 64, 15, 75, 67, 88};

        int size = a.length;
        System.out.print("Before Sorting : ");
        display(a, size);

        mergeSort(a, 0, size - 1);

        System.out.print("After Sorting : ");
        display(a, size);
    }

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

            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int i, j, k;
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];

        i = 0; j = 0; k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }
        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }
}

	
Before Sorting :
11 9 6 19 33 64 15 75 67 88 
After Sorting :
6 9 11 15 19 33 64 67 75 88

Quick Facts about Merge Sort

Time complexity: O(n log n) in best, average and worst cases.
Suitable for external sorting (large data on disk).
Stability: Merge sort is stable if implemented appropriately.
Requires additional memory for merging (extra O(n) space for typical implementations).

Pros

Consistent O(n log n) performance.
Well suited for large datasets and external sorting.
Stable sort (when implemented to preserve equal keys' order).

Cons

Extra O(n) space required for merging (in-place variants exist but are complex).
Overhead of recursion and temporary arrays — may be slower than in-place algorithms for small arrays.

Time Complexity Summary

Best	Average	Worst	Space Complexity
O(n log n)	O(n log n)	O(n log n)	O(n)

Footer Content | CrackEase

→

←

Courses

Chapters

Data Structure

Sorting

Linked List

Stack

Queue

Tree

Merge Sort

Merge Sort