📘 Lesson · Lesson 79

Merge Sort

💡 Note

Merge sort divides the array in half, sorts each half, then merges them — a fast O(n log n) sort.

Program

C++

#include <iostream>
using namespace std;
void merge(int a[], int l, int m, int r) {
    int L[20], R[20], n1=m-l+1, n2=r-m;
    for(int i=0;i<n1;i++) L[i]=a[l+i];
    for(int j=0;j<n2;j++) R[j]=a[m+1+j];
    int i=0,j=0,k=l;
    while(i<n1&&j<n2) a[k++]=(L[i]<=R[j])?L[i++]:R[j++];
    while(i<n1) a[k++]=L[i++];
    while(j<n2) a[k++]=R[j++];
}
void mergeSort(int a[], int l, int r) {
    if(l<r){ int m=(l+r)/2; mergeSort(a,l,m); mergeSort(a,m+1,r); merge(a,l,m,r); }
}

Summary

Divide the array, sort halves recursively, then merge sorted halves.
Time complexity O(n log n) — faster than bubble/selection for large data.

Merge Sort

💡 Note

Merge sort array को आधा बाँटता है, हर आधा sort करता है, फिर merge करता है — तेज़ O(n log n) sort।

Program

C++

#include <iostream>
using namespace std;
void merge(int a[], int l, int m, int r) {
    int L[20], R[20], n1=m-l+1, n2=r-m;
    for(int i=0;i<n1;i++) L[i]=a[l+i];
    for(int j=0;j<n2;j++) R[j]=a[m+1+j];
    int i=0,j=0,k=l;
    while(i<n1&&j<n2) a[k++]=(L[i]<=R[j])?L[i++]:R[j++];
    while(i<n1) a[k++]=L[i++];
    while(j<n2) a[k++]=R[j++];
}
void mergeSort(int a[], int l, int r) {
    if(l<r){ int m=(l+r)/2; mergeSort(a,l,m); mergeSort(a,m+1,r); merge(a,l,m,r); }
}

सारांश

Array बाँटें, halves recursively sort करें, फिर sorted halves merge करें।
Time complexity O(n log n) — बड़े data के लिए bubble/selection से तेज़।

← Back to C++ Tutorial