মার্জ সোর্ট (Merge Sort) হল একটি সোর্টিং অ্যালগরিদম যা ভাগ করুন ও জিতুন (divide and conquer) পদ্ধতি ব্যবহার করে। এটি অ্যারেটিকে দুটি অংশে ভাগ করে এবং তারপর এই দুটি অংশের জন্য নিজে নিজে কল করে। এই প্রক্রিয়া অ্যারেটি সাজানো পর্যন্ত চলতে থাকে।
উদাহরণ
using System;
namespace QuickSortDemo {
class Example {
static public void merge(int[] arr, int p, int q, int r) {
int i, j, k;
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[p + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[q + 1 + j];
}
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
static public void mergeSort(int[] arr, int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSort(arr, p, q);
mergeSort(arr, q + 1, r);
merge(arr, p, q, r);
}
}
static void Main(string[] args) {
int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
int n = 10, i;
Console.WriteLine("Merge Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
mergeSort(arr, 0, n-1);
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
}
আউটপুট
Merge Sort Initial array is: 76 89 23 1 55 78 99 12 65 100 Sorted Array is: 1 12 23 55 65 76 78 89 99 100
প্রোগ্রাম ব্যাখ্যা
Main() ফাংশনে, প্রথমে প্রাথমিক অ্যারেটি প্রদর্শন করা হয়। তারপর mergeSort() ফাংশনটি কল করা হয় অ্যারেটি সাজানোর জন্য।
mergeSort() ফাংশনে, q অ্যারেতির মধ্যবিন্দু হিসেবে গণনা করা হয়। তারপর mergeSort() উভয় সাব-অ্যারেতে কল করা হয়। অবশেষে merge() কল করা হয় যা এই সাব-অ্যারেগুলোকে একত্রিত করে।
merge() ফাংশনে, দুটি সাজানো সাব-অ্যারে প্রদান করা হয়। এই ফাংশনটি মূলত এই সাব-অ্যারেগুলোকে একটি একক অ্যারেতে একত্রিত করে যাতে ফলাফল অ্যারেটিও সাজানো থাকে।
