Merge Sort Program with Explanation and Code

2025-11-19 merge sort sorting algorithms divide and conquer stable sorting recursive sort array sorting python merge sort c merge sort javascript sorting php merge sort csharp merge sort algorithm explanation data structures

Merge Sort is a fast and stable divide-and-conquer sorting algorithm. This page explains the concept step-by-step and includes complete Merge Sort program examples in Python, C, JavaScript, PHP, and C#. Ideal for students and interview preparation.

Program Explanation

What is Merge Sort?

Merge Sort is a popular, efficient, and stable divide-and-conquer sorting algorithm. It works by recursively splitting the array into halves, sorting each half, and then merging the sorted halves back together. Merge Sort guarantees O(n log n) time complexity in all cases.

Steps to Solve

  1. Divide the array into two halves.
  2. Recursively apply Merge Sort on the left half.
  3. Recursively apply Merge Sort on the right half.
  4. Merge the two sorted halves into a single sorted array.
  5. Continue merging until the entire array is sorted.
  6. Base condition: if the array has 0 or 1 element → it is already sorted.

Key Points

  • Merge Sort always has time complexity O(n log n).
  • It is a stable sorting algorithm.
  • Requires additional memory for merging.
  • Best suited for large datasets where stability is important.
  • Works well with linked lists as well.
  • Uses divide-and-conquer strategy.

Program Code


def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    sorted_arr = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    return sorted_arr

arr = list(map(int, input("Enter numbers: ").split()))
print("Sorted array:", merge_sort(arr))
      

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

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;

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

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter numbers: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    mergeSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function merge(left, right) {
  let sorted = [], i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) sorted.push(left[i++]);
    else sorted.push(right[j++]);
  }

  return [...sorted, ...left.slice(i), ...right.slice(j)];
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
console.log("Sorted array:", mergeSort(arr));
      

using System;
using System.Linq;

class Program {

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

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

        Array.Copy(arr, left, L, 0, n1);
        Array.Copy(arr, mid + 1, R, 0, n2);

        int 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++];
    }

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

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();

        MergeSort(arr, 0, arr.Length - 1);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function mergeSort($arr) {
    if (count($arr) <= 1)
        return $arr;

    $mid = intval(count($arr) / 2);
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));

    return mergeArrays($left, $right);
}

function mergeArrays($left, $right) {
    $sorted = [];
    $i = $j = 0;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j])
            $sorted[] = $left[$i++];
        else
            $sorted[] = $right[$j++];
    }

    return array_merge($sorted, array_slice($left, $i), array_slice($right, $j));
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
$result = mergeSort($arr);

echo "Sorted array: " . implode(" ", $result);

?>
1