Merge Sort একটি Divide and Conquer (বিভাজন করে জয় করা) ভিত্তিক এলগরিদম। এটি একটি recursive পদ্ধতিতে কাজ করে যেখানে একটি অ্যারে বারবার অর্ধেক করে ভাগ করা হয় যতক্ষণ না একক উপাদানে নেমে আসে, এরপর সেগুলোকে সঠিকভাবে merge করে সাজানো হয়।

* মনে রাখতে হবে, একক উপাদান (single element) সবসময় sorted থাকে। তাই merge করার সময় কেবল দুটি sorted উপাদানকে মিলিয়ে বড় sorted array তৈরি করতে হয়।

public class MergeSortExample {

    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 2, 9, 1, 3, 7};
        mergeSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

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

    private 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];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];

        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int 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++];
    }
}

Step-by-Step Merge Sort Process:

arr = {8, 4, 5, 2, 9, 1, 3, 7}

total elements = 8

Left index = 0, Right index = 7

 Step 1: mergeSort(arr, 0, 7)

• (0 < 7) → সত্য
• mid = (0 + 7)/2 = 3
• দুটি ভাগ:
  • mergeSort(arr, 0, 3)
  • mergeSort(arr, 4, 7)

Step 2: mergeSort(arr, 0, 3)

• (0 < 3) → সত্য
• mid = 1
• দুটি ভাগ:
  • mergeSort(arr, 0, 1)
  • mergeSort(arr, 2, 3)

 Step 3: mergeSort(arr, 0, 1)

• (0 < 1) → সত্য
• mid = 0
  • mergeSort(arr, 0, 0) → return
  • mergeSort(arr, 1, 1) → return
• merge(arr, 0, 0, 1) → {8, 4} → {4, 8}

Step 4: mergeSort(arr, 2, 3)

• (2 < 3) → সত্য
• mid = 2
  • mergeSort(arr, 2, 2) → return
  • mergeSort(arr, 3, 3) → return
• merge(arr, 2, 2, 3) → {5, 2} → {2, 5}

Step 5:

merge(arr, 0, 1, 3) → {4, 8}, {2, 5} → merge → {2, 4, 5, 8}

 Step 6: mergeSort(arr, 4, 7)

• mid = 5
  • mergeSort(arr, 4, 5) → mid = 4
    • mergeSort(arr, 4, 4) → return
    • mergeSort(arr, 5, 5) → return
    • merge(arr, 4, 4, 5) → {9, 1} → {1, 9}
  • mergeSort(arr, 6, 7) → mid = 6
    • mergeSort(arr, 6, 6) → return
    • mergeSort(arr, 7, 7) → return
    • merge(arr, 6, 6, 7) → {3, 7} → {3, 7}

Step 7:

merge(arr, 4, 5, 7) → {1, 9}, {3, 7} → merge → {1, 3, 7, 9}

Step 8 (Final):

merge(arr, 0, 3, 7) → {2, 4, 5, 8}, {1, 3, 7, 9} → merge →  Final Sorted Array:

[1, 2, 3, 4, 5, 7, 8, 9]

Merge Sort Time complexity:

ধরা যাক একটা অ্যারেতে n সংখ্যক উপাদান আছে।

Merge Sort-এর ধারণা হলো — আমরা এই অ্যারেটাকে প্রতিবার অর্ধেক করি যতক্ষণ না সব উপাদান একা হয়ে যায়। এরপর সেই একক উপাদানগুলোকে merge করে আবার বড় বড় sorted অ্যারে তৈরি করি।

এখন প্রতিটি লেভেলে, যত টুকরোই থাকুক না কেন, সব মিলিয়ে সব n উপাদানকেই একবার না একবার compare/copy করতে হয়।

উদাহরণ:

n = 8

Level 3:  [8] [3] [1] [7] [0] [10] [2] [5]   → মোট ৮টা 1-সাইজের টুকরো

Level 2:  [3,8] [1,7] [0,10] [2,5]           → মোট ৪টা 2-সাইজের merge

Level 1:  [1,3,7,8] [0,2,5,10]               → ২টা 4-সাইজের merge

Level 0:  [0,1,2,3,5,7,8,10]                 → ১টা 8-সাইজের merge

প্রতিটি লেভেল-এ মিলিয়ে সব উপাদান একবার না একবার process হচ্ছে, তাই প্রতি লেভেলে সময় লাগে:

 O(n)

প্রতিবার অ্যারে অর্ধেক হয়ে যাচ্ছে:

n → n/2 → n/4 → n/8 → … → 1

এই ধারায় যতবার n কে ২ দিয়ে ভাগ করলে ১-এ পৌঁছায়, সেই সংখ্যাটাই হচ্ছে Merge Sort-এর Level Count।

এটি log₂(n) — যার মানে:

n উপাদানকে ২ দিয়ে ভাগ করলে যতবার ভাগ করতে হবে = log₂(n)

উদাহরণ:

n	Level	কারণ
8	3	8→4→2→1
16	4	16→8→4→2→1
32	5	32→16→8→4→2→1

তাই total level = log₂(n)

তাহলে

1. প্রতি level = O(n)
2. মোট level = log₂(n)

Total Time = O(n) + O(n) + … log₂(n) বার,   মানে:  Total Time = O(n) × log₂(n)

 Big-O লেখায় base বাদ দেওয়া যায় (যতক্ষণ না log এর base change হচ্ছে), এবং গুণফল সরাসরি লেখা যায়।

Final time complexity: O(n log n)