কনটেন্টে যান

Merge sort — sorted অংশ জোড়া

  • Original source: এই repository-র নিজস্ব অনুশীলন
  • Topic: sorting / searching
  • Difficulty: Easy
  • Pattern: divide and conquer / merge
  • Course: Microsoft · Module 2-এর topic অনুশীলন; official assignment নয়

প্রশ্ন ও উদাহরণ

একটি integer list দেওয়া আছে। মূল list না বদলে ছোট থেকে বড় ক্রমে নতুন list ফেরত দিন; শেখার জন্য নির্দিষ্ট algorithm-টি নিজে লিখুন। Empty input ও duplicate থাকতে পারে। হাতে trace করার সময় সর্বোচ্চ 8টি মান নিন; lab report-এ সর্বোচ্চ 200টি product।

  • Input: [4, 1, 3, 2]
  • Output: [1, 2, 3, 4]

ভিত্তির ধারণা

আগে পড়ুন: sorting/searching-এর ধারণা, array ও index। এরপর divide and conquer / merge-এর কাজটি নিজের ভাষায় বলুন।

প্রথমে এক ঘরের block-গুলো sorted। Width 1-এর দুটি block merge করে width 2 করুন; তারপর width 4। দুই front-এর ছোটটি নিলে result-এর পরের সঠিক মান পাওয়া যায়।

ধাপে ধাপে সমাধান

ধাপ Block
width 1 [4] [1] [3] [2]
width 2 [1,4] [2,3]
width 4 1, তারপর 2, তারপর 3, শেষে 4 → [1,2,3,4]

Checkpoint: পরের তুলনা code চালানোর আগে নিজে লিখুন। কোন অংশ আর বদলাবে না, সেটি চিহ্নিত করুন।

ইঙ্গিত: সমান key-তে বাঁয়ের item আগে নিন; তাহলে stable order থাকবে। Odd সংখ্যক block থাকলে অবশিষ্টটুকুও নিতে হবে।

কোড ও ব্যাখ্যা

সম্পূর্ণ implementation আছে sorting_lab.py-এ। Repository root থেকে নিচের ছোট example চালানো যায়:

Python
from practice.sorting_lab import merge_sort

print(merge_sort([4, 1, 3, 2]))

প্রথমে reference না দেখে function লিখুন। পরে loop boundary ও কোন অবস্থায় pointer বাড়ছে তা reference-এর সঙ্গে মিলিয়ে দেখুন।

খরচ ও সাধারণ ভুল

O(n log n) time, O(n) extra space; reference bottom-up, তাই recursion লাগে না।

Empty list, একই মান বারবার, আগে থেকেই sorted, উল্টো sorted এবং একটিমাত্র element পরীক্ষা করুন। Input list ভুল করে বদলে যাচ্ছে কি না তাও দেখুন।

শেখা ও পরের অনুশীলন

পরীক্ষাগুলো দিয়ে output, stability ও edge case মিলিয়ে নিন:

Bash
python -m unittest discover -s practice -p "test_sorting_lab.py" -v

তারপর পণ্যের catalogue guided challenge-এ একই algorithm বাস্তব query-র সঙ্গে ব্যবহার করুন। তালিকায় ফিরুন।