জাভাস্ক্রিপ্টে মার্জ সর্ট রিকার্সিভ ইমপ্লিমেন্টেশন

মার্জ সর্ট অ্যালগরিদম

দুই অংশে ভাগ করা হয়:

1. রিকার্সিভ পার্ট: অ্যারেকে একক এলিমেন্ট পর্যন্ত ভাগ করা।
2. ইটেরেটিভ পার্ট: সর্টেড সাব-অ্যারেগুলো মার্জ করে ফাইনাল সর্টেড অ্যারে বানানো।

সমাধান

const arr = [23, 4, 67, 32, 1, 7, 56, 5, 89];

const mergeSort = arr => {
  if (arr.length < 2) return arr;
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle, arr.length);
  return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
  const res = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) res.push(left.shift());
    else res.push(right.shift());
  }
  while (left.length) res.push(left.shift());
  while (right.length) res.push(right.shift());
  return res;
};

console.log(mergeSort(arr));

আউটপুট

[ 1, 4, 5, 7, 23, 32, 56, 67, 89 ]

কমপ্লেক্সিটি

• টাইম: O(n log n) সব কেসে।
• স্পেস: O(n) (অক্সিলিয়ারি অ্যারে জন্য)।
• স্টেবল সর্ট (সমান এলিমেন্টের রিলেটিভ অর্ডার বজায় থাকে)।