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

<div class="problem-source" markdown="1">

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

</div>

## প্রশ্ন ও উদাহরণ {#problem}

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

- Input: `[4, 1, 3, 2]`
- Output: `[1, 2, 3, 4]`

## ভিত্তির ধারণা {#idea}

আগে পড়ুন: [sorting/searching-এর ধারণা](../concept.md), [array ও index](../../02-arrays-and-strings/concept.md)। এরপর `divide and conquer / merge`-এর কাজটি নিজের ভাষায় বলুন।

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

## ধাপে ধাপে সমাধান {#walkthrough}

| ধাপ | 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 থাকলে অবশিষ্টটুকুও নিতে হবে।

## কোড ও ব্যাখ্যা {#code}

সম্পূর্ণ implementation আছে [sorting_lab.py](../../practice/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-এর সঙ্গে মিলিয়ে দেখুন।

## খরচ ও সাধারণ ভুল {#cost}

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

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

## শেখা ও পরের অনুশীলন {#practice}

[পরীক্ষাগুলো](../../practice/test_sorting_lab.py) দিয়ে output, stability ও edge case মিলিয়ে নিন:

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

তারপর [পণ্যের catalogue guided challenge](../../guided-practice/sorting-searching.md)-এ একই algorithm বাস্তব query-র সঙ্গে ব্যবহার করুন। [তালিকায় ফিরুন](../README.md)।