মার্জ সর্ট (Merge sort) হলো একটি সোর্টিং টেকনিক। এটি একটি দক্ষ সোর্টিং অ্যালগরিদম যার টাইম কমপ্লেক্সিটি O(n log n) (এখানে n হলো সর্ট করার অ্যারেের দৈর্ঘ্য)।
মার্জ সর্ট একটি অ্যালগরিদম যা Divide and Conquer প্যারাডাইম অনুসরণ করে। এটি liên tục অ্যারে দুটি সমান আধারে ভাগ করে। পরে একক এলিমেন্ট 가진 লিস্টগুলো সর্ট করা শুরু করে এবং ক্রমাগত সর্ট করা লিস্টগুলো মার্জ করে পূর্ণ সর্ট করা লিস্ট গঠন করে।
এভাবেই আমরা একটি সর্ট করা অ্যারে পাই।
উদাহরণ
বেগুনি বক্স এবং কালো তীর লিস্টকে দুটি আধারে ভাগ করার প্রক্রিয়া দেখাচ্ছে।
সবুজ বক্স এবং লাল তীর দুটি সর্ট করা লিস্ট মার্জ করার প্রক্রিয়া দেখাচ্ছে।
মার্জ সর্ট ইমপ্লিমেন্টেশন
লিস্টকে দুটি আধারে ভাগ করা সহজ এবং এটি রিকার্সিভলি করা হয় যতক্ষণ না একক এলিমেন্ট থাকা পর্যন্ত। পরে মার্জিং প্রসিডিউর করা হয় যা আসলে دوটি সর্ট করা লিস্ট একসাথে মার্জ করার লজিক প্রয়োগ করা হয়।
উদাহরণ
merge ফাংশন মার্জ করার দুটি সর্ট করা অ্যারে নেয়। a1-এর ফ্রন্টমোস্ট এলিমেন্ট a2-এর ফ্রন্টমোস্ট এলিমেন্টের সাথে তুলনা করা হয়। দুইটির মধ্যে ছোটটি লিস্ট c-তে যোগ করা হয় এবং সেই অ্যারের পয়েন্টার ইনক্রিমেন্ট করা হয়।
def merge(a1, a2):
c = []
x = 0
y = 0
while x < len(a1) and y < len(a2):
if a1[x] < a2[y]:
c.append(a1[x])
x += 1
else:
c.append(a2[y])
y += 1
while x < len(a1):
c.append(a1[x])
x += 1
while y < len(a2):
c.append(a2[y])
y += 1
return c
def mergesort(array):
if len(array) == 1:
return array
mid = len(array) // 2
a1 = mergesort(array[:mid])
a2 = mergesort(array[mid:])
return merge(a1, a2)
array = [2, 3, 1, 5, 4, 6, 8, 10, 7, 9]
print(mergesort(array))
আউটপুট
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
