Merge Sort in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include<stdio.h>

void m(int a[], int l, int m, int r) {
    int b[100], i = l, j = m+1, k = 0;
    while(i <= m && j <= r)
        b[k++] = a[i] < a[j] ? a[i++] : a[j++];
    while(i <= m) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    for(i = 0; i < k; i++) a[l+i] = b[i];
}

void s(int a[], int l, int r) {
    if(l < r) {
        int m = (l+r)/2;
        s(a,l,m); s(a,m+1,r); m(a,l,m,r);
    }
}

int main() {
    int a[100], n;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    s(a,0,n-1);
    for(int i=0; i<n; i++) printf("%d ", a[i]);
}

C Output

Input:  
6  
5 2 8 1 4 3  

Output:  
1 2 3 4 5 8

C++ Program

#include<iostream>
using namespace std;

void m(int a[], int l, int m, int r) {
    int b[100], i=l, j=m+1, k=0;
    while(i<=m && j<=r) b[k++] = a[i]<a[j] ? a[i++] : a[j++];
    while(i<=m) b[k++] = a[i++];
    while(j<=r) b[k++] = a[j++];
    for(i=0; i<k; i++) a[l+i] = b[i];
}

void s(int a[], int l, int r) {
    if(l<r) {
        int m=(l+r)/2;
        s(a,l,m); s(a,m+1,r); m(a,l,m,r);
    }
}

int main() {
    int a[100], n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    s(a,0,n-1);
    for(int i=0; i<n; i++) cout << a[i] << " ";
}

C++ Output

Input:  
5  
10 1 8 3 4  

Output:  
1 3 4 8 10

JAVA Program

import java.util.*;

class M {
    static void merge(int a[], int l, int m, int r) {
        int[] b = new int[r-l+1];
        int i=l, j=m+1, k=0;
        while(i<=m && j<=r) b[k++] = a[i]<a[j] ? a[i++] : a[j++];
        while(i<=m) b[k++] = a[i++];
        while(j<=r) b[k++] = a[j++];
        for(i=0; i<k; i++) a[l+i] = b[i];
    }

    static void sort(int a[], int l, int r) {
        if(l<r) {
            int m=(l+r)/2;
            sort(a,l,m); sort(a,m+1,r); merge(a,l,m,r);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), a[] = new int[n];
        for(int i=0; i<n; i++) a[i] = sc.nextInt();
        sort(a,0,n-1);
        for(int i=0; i<n; i++) System.out.print(a[i]+" ");
    }
}

JAVA Output

Input:  
4  
7 2 9 5  

Output:  
2 5 7 9

Python Program

def msort(a):
    if len(a) <= 1: return a
    m = len(a)//2
    l = msort(a[:m])
    r = msort(a[m:])
    res = []
    while l and r:
        res.append((l if l[0]<r[0] else r).pop(0))
    return res + l + r

print(*msort(list(map(int, input().split()))))

Python Output

Input:  
8 4 1 7  

Output:  
1 4 7 8

In-Depth Learning – Full Concept in Paragraphs

What Is Merge Sort?

Merge Sort is a fast, stable, comparison-based, divide-and-conquer sort algorithm. It splits the array in halves, recursively sorts both halves, and ultimately combines the halves in sorted order to generate the sorted array. It's extremely efficient for big data sets and provides assured performance irrespective of the input ordering.

How the Code Works

The merge sort algorithm involves two key steps:

Divide: The array is split into two halves until every sub-array contains a single element.

Conquer & Merge: Merged halves are combined back in sorted order.

The merge() function does all the heavy lifting by comparing and merging elements in sorted order. It stores the merged result in an extra array (b[]) and then copies it back into the original array.

Example

Let's sort:

csharp

Copy

Edit

[5, 2, 8, 1]

Split into: [5, 2] and [8, 1]

Split further: [5], [2], [8], [1]

Recombine:

[5] + [2] → [2, 5]

[8] + [1] → [1, 8]

[2, 5] + [1, 8] → [1, 2, 5, 8]

The process guarantees sorted order at every level of merging.

Real-Life Analogy

Suppose two individuals are sorting cards. Each has sorted stacks. In order to form a final sorted stack, they take the lowest card from the top of both stacks and put it into a new merged stack. They continue doing so until both stacks run out — that is how merging occurs in Merge Sort.

Where and When Is It Used?

Merge Sort is the best when:

You require predictable performance (assured O(n log n))

You work with linked lists (easy to implement in-place merges)

Sorting large files (external sorting)

It is used in:

Libraries (e.g., Java’s TimSort partially uses it)

Databases, memory-limited systems

Competitive programming, system-level sorting

Time Complexity

Case Time

Best O(n log n)

Average O(n log n)

Worst O(n log n)

Space O(n) (due to extra array during merging)

Unlike Quick Sort, Merge Sort doesn't degrade in performance even in the worst case.

Python-Specific Advantage

Python makes recursive thinking and merging with slicing and list operations easy. Its readability and presence of built-in functions make Merge Sort learning simpler than in any other language.

SEO-Optimized Natural Paragraph for Ranking

Looking for the most straightforward explanation of Merge Sort with code that works? This tutorial offers Merge Sort in C, C++, Java, and Python in the shortest, easiest manner. Merge Sort is a stable and efficient sorting algorithm founded on the divide-and-conquer paradigm. It divides the array recursively and merges sorted segments into a single sorted array. As a beginner to recursion or an interviewee, Merge Sort imparting fundamental algorithmic knowledge is perfect for performance-critical use cases. Master sorting logic and time complexity with these real-world examples and explanations.