# فصل ۰۳ — دو مرتب‌سازیِ `O(n²)` که باید یک بار با دست انجامشان بدهی

<div dir="rtl">

# فصل ۰۳ — دو مرتب‌سازیِ `O(n²)` که باید یک بار با دست انجامشان بدهی

## در این فصل چه یاد می‌گیری

دو الگوریتمِ مرتب‌سازی می‌نویسیم که هر دو ساده‌اند، هر دو درست کار می‌کنند، و هر دو `O(n²)` هستند. **هدف این نیست که در کارِ واقعی به‌کارشان ببری؛ هدف این است که یک بار با دست انجامشان بدهی** — چون بدونِ این، فصل‌های ۴ و ۵ فقط دو طلسمِ حفظی می‌شوند.

و همان‌جا اولین درسِ واقعیِ مرتب‌سازی درمی‌آید: **در `n = 2,000` یکی `1,999,000` مقایسه می‌کند و دیگری `1,022,176`.** ولی وقتی ورودی از پیش مرتب باشد، دومی همان عدد را به **`1,999`** می‌رساند و ستونِ نسبتش `2.00` می‌شود، و اولی **مو نمی‌زند**.

![دو دستِ مرتب‌کنندهٔ کارت که یکی کوچک‌ترین کارت را بیرون می‌کشد و دیگری کارتِ بعدی را در جای درستش می‌نشاند](/lesson-assets/t4-s03-quadratic-sorts/prompt/01-image-two-sorting-hands.png)

آخر این فصل می‌توانی:

- `selection sort` و `insertion sort` را از صفر بنویسی
- ناوردای حلقهٔ هرکدام را بگویی و در خروجی نشانش بدهی
- تعدادِ مقایسه را از تعدادِ جابه‌جایی جدا کنی و بگویی چرا این تفکیک مهم است
- بگویی چرا «بدترین حالت» و «حالتی که واقعاً داری» برای این دو الگوریتم یکی نیستند

## قبل از شروع

**از ترمِ ۱ فصلِ ۴:** شمارندهٔ عملیات، و اینکه شمارش قطعی است و ثانیه نیست.

**از ترمِ ۳ فصلِ ۴:** سه پرسشِ متفاوت — بدترین حالت، حالتِ متوسط، و حالتی که واقعاً داری. **این فصل همان سه پرسش را روی مرتب‌سازی تکرار می‌کند** و می‌بینی جوابشان برای دو الگوریتمِ هم‌مرتبه کاملاً فرق دارد.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-4-recursion-sorting-searching/session-03-quadratic-sorts.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. `selection sort` با دست

ایده‌اش همان کاری است که با یک دسته کارت می‌کنی: **کوچک‌ترین را پیدا کن، بگذارش اول؛ از بقیه کوچک‌ترین را پیدا کن، بگذارش دوم؛ و همین‌طور تا آخر.**

</div>

```python
def selection_sort_traced(values):
    """در هر پاس، کوچک‌ترینِ باقی‌مانده را به جای درستش می‌آورد."""
    a = list(values)
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]
        print(f"پاس {i + 1}: {a}   <- {i + 1} عضوِ اول برای همیشه سرِ جایشان‌اند")
    return a


start = [29, 10, 14, 37, 13, 25, 11, 18]
print("ورودی :", start)
print()
print("خروجی :", selection_sort_traced(start))
```

```text
ورودی : [29, 10, 14, 37, 13, 25, 11, 18]

پاس 1: [10, 29, 14, 37, 13, 25, 11, 18]   <- 1 عضوِ اول برای همیشه سرِ جایشان‌اند
پاس 2: [10, 11, 14, 37, 13, 25, 29, 18]   <- 2 عضوِ اول برای همیشه سرِ جایشان‌اند
پاس 3: [10, 11, 13, 37, 14, 25, 29, 18]   <- 3 عضوِ اول برای همیشه سرِ جایشان‌اند
پاس 4: [10, 11, 13, 14, 37, 25, 29, 18]   <- 4 عضوِ اول برای همیشه سرِ جایشان‌اند
پاس 5: [10, 11, 13, 14, 18, 25, 29, 37]   <- 5 عضوِ اول برای همیشه سرِ جایشان‌اند
پاس 6: [10, 11, 13, 14, 18, 25, 29, 37]   <- 6 عضوِ اول برای همیشه سرِ جایشان‌اند
پاس 7: [10, 11, 13, 14, 18, 25, 29, 37]   <- 7 عضوِ اول برای همیشه سرِ جایشان‌اند
خروجی : [10, 11, 13, 14, 18, 25, 29, 37]
```

<div dir="rtl">

**جملهٔ سمتِ راستِ هر سطر یک «ناوردای حلقه» است:** چیزی که قبل از هر دورِ حلقه درست است و بعد از آن هم درست می‌ماند. ناوردای `selection sort` این است: **`i` عضوِ اول کوچک‌ترین‌های کلِ فهرست‌اند و دیگر هیچ‌وقت تکان نمی‌خورند.** وقتی حلقه تمام شود، `i` برابرِ طولِ فهرست است و همین جمله می‌شود «همه‌چیز مرتب است».

**و دو سطرِ آخر را ببین: فهرست از پاسِ ۵ مرتب بود و الگوریتم دو پاسِ دیگر هم رفت.** `selection sort` هیچ راهی ندارد که بفهمد کارش تمام شده — **چون برای پیدا کردنِ کوچک‌ترین، باید همه را ببیند.** این جمله را نگه دار؛ در بخشِ ۴ به یک عدد تبدیل می‌شود.

## ۲. `insertion sort` با دست

ایدهٔ دوم هم از کارت‌بازی می‌آید، ولی از طرفِ دیگر: **کارت‌های دستِ چپت مرتب‌اند؛ کارتِ بعدی را بردار و در جای درستش بینشان بنشان.**

</div>

```python
def insertion_sort_traced(values):
    """هر عضو را در جای درستش بینِ عضوهای مرتب‌شدهٔ سمتِ چپ می‌نشاند."""
    a = list(values)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
        print(f"پاس {i}: {a}   <- {i + 1} عضوِ اول نسبت به هم مرتب‌اند")
    return a


print("ورودی :", start)
print()
print("خروجی :", insertion_sort_traced(start))
```

```text
ورودی : [29, 10, 14, 37, 13, 25, 11, 18]

پاس 1: [10, 29, 14, 37, 13, 25, 11, 18]   <- 2 عضوِ اول نسبت به هم مرتب‌اند
پاس 2: [10, 14, 29, 37, 13, 25, 11, 18]   <- 3 عضوِ اول نسبت به هم مرتب‌اند
پاس 3: [10, 14, 29, 37, 13, 25, 11, 18]   <- 4 عضوِ اول نسبت به هم مرتب‌اند
پاس 4: [10, 13, 14, 29, 37, 25, 11, 18]   <- 5 عضوِ اول نسبت به هم مرتب‌اند
پاس 5: [10, 13, 14, 25, 29, 37, 11, 18]   <- 6 عضوِ اول نسبت به هم مرتب‌اند
پاس 6: [10, 11, 13, 14, 25, 29, 37, 18]   <- 7 عضوِ اول نسبت به هم مرتب‌اند
پاس 7: [10, 11, 13, 14, 18, 25, 29, 37]   <- 8 عضوِ اول نسبت به هم مرتب‌اند
خروجی : [10, 11, 13, 14, 18, 25, 29, 37]
```

<div dir="rtl">

**ناوردای این یکی ضعیف‌تر است و همین ضعف قدرتش است.** `insertion sort` نمی‌گوید «این‌ها سرِ جای نهایی‌شان‌اند»؛ فقط می‌گوید «این‌ها **نسبت به هم** مرتب‌اند». در پاسِ ۶ عددِ `11` از انتها آمد و همه را یک خانه هل داد — کاری که `selection sort` هرگز لازم ندارد.

**و به پاسِ ۳ دقت کن: هیچ چیزی تکان نخورد.** `37` از قبل بزرگ‌تر از همسایه‌اش بود، پس حلقهٔ داخلی همان اول ایستاد. **این تنها جایی است که یکی از این دو الگوریتم می‌تواند کارِ کمتری بکند** — و بخشِ ۵ نشان می‌دهد چقدر کمتر.

## ۳. دو شمارنده، نه یکی

هزینهٔ مرتب‌سازی دو جزء دارد و **جمع کردنشان در یک عدد، اطلاعات را از بین می‌برد**: تعدادِ **مقایسه** (چند بار پرسیدیم «کدام بزرگ‌تر است؟») و تعدادِ **جابه‌جایی** (چند بار داده را واقعاً حرکت دادیم).

</div>

```python
def selection_sort(values):
    """مرتب‌شده، تعدادِ مقایسه، تعدادِ جابه‌جایی."""
    a = list(values)
    comparisons = swaps = 0
    n = len(a)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            comparisons += 1
            if a[j] < a[smallest]:
                smallest = j
        if smallest != i:
            a[i], a[smallest] = a[smallest], a[i]
            swaps += 1
    return a, comparisons, swaps


def insertion_sort(values):
    """مرتب‌شده، تعدادِ مقایسه، تعدادِ جابه‌جایی."""
    a = list(values)
    comparisons = moves = 0
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if a[j] <= key:
                break
            a[j + 1] = a[j]
            moves += 1
            j -= 1
        a[j + 1] = key
    return a, comparisons, moves


rng = random.Random(SEED)
LADDER = [250, 500, 1_000, 2_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in LADDER}
check = shuffled[250]
print("هر دو با sorted یکی درمی‌آیند؟",
      selection_sort(check)[0] == insertion_sort(check)[0] == sorted(check))
print("مقایسهٔ selection در n=250:", selection_sort(check)[1])
print("مقایسهٔ insertion در n=250:", insertion_sort(check)[1])
```

```text
هر دو با sorted یکی درمی‌آیند؟ True
مقایسهٔ selection در n=250: 31125
مقایسهٔ insertion در n=250: 14113
```

<div dir="rtl">

**سطرِ اول قبل از هر جدولی می‌آید.** دو الگوریتمی که جوابِ متفاوت بدهند، اصلاً قابلِ مقایسه نیستند.

> 🤔 **اول حدس بزن:** برای `selection sort`، ستونِ نسبتِ **مقایسه** و ستونِ نسبتِ **جابه‌جایی** را جدا حدس بزن. **دو عددِ متفاوت بنویس**، بعد جدول را ببین.

## ۴. `selection sort`: مقایسهٔ زیاد، جابه‌جاییِ کم

</div>

```python
print("— selection sort: مقایسه")
table([(n, selection_sort(shuffled[n])[1]) for n in LADDER], "مقایسه", ",d")
print("\n— selection sort: جابه‌جایی")
table([(n, selection_sort(shuffled[n])[2]) for n in LADDER], "جابه‌جایی", ",d")
```

```text
— selection sort: مقایسه
         n            مقایسه     نسبت به سطر قبل
       250            31,125                   —
       500           124,750                4.01
     1,000           499,500                4.00
     2,000         1,999,000                4.00

— selection sort: جابه‌جایی
         n         جابه‌جایی     نسبت به سطر قبل
       250               240                   —
       500               495                2.06
     1,000               997                2.01
     2,000             1,989                1.99
```

<div dir="rtl">

**`4.00` برای مقایسه و `2.00` برای جابه‌جایی — یک الگوریتم، دو مرتبهٔ متفاوت.**

مقایسه‌ها `O(n²)` هستند چون در هر پاس کلِ باقی‌مانده باید دیده شود. جابه‌جایی‌ها `O(n)` هستند چون **هر پاس حداکثر یک جابه‌جایی دارد** — و اگر کوچک‌ترین از قبل سرِ جایش باشد، هیچ. برای همین است که عددِ سطرِ آخر `1,989` است و نه `1,999`: ده پاس اصلاً جابه‌جایی نخواستند.

**و این تفکیک عملی است، نه تزئینی:** اگر جابه‌جا کردنِ یک عضو خیلی گران باشد (مثلاً هر عضو یک رکوردِ بزرگ باشد)، `selection sort` با اینکه «کند» است، کمترین حرکتِ ممکن را انجام می‌دهد. **مرتبهٔ کلی یک عدد است؛ تصمیم با دو عدد گرفته می‌شود.**

## ۵. حالا ورودی را عوض کن

اول همان ورودیِ تصادفیِ بخشِ ۴، این بار برای الگوریتمِ دوم.

> 🤔 **اول حدس بزن:** `insertion sort` روی ورودیِ تصادفی. **دو عدد بنویس** — ستونِ نسبتِ مقایسه و ستونِ نسبتِ جابه‌جایی — و بعد یک حدسِ سوم که مهم‌تر از هر دو است: **نسبتِ جابه‌جایی‌های این الگوریتم به جابه‌جایی‌های `selection sort` در `n = 2,000` چقدر است؟**

</div>

```python
print("— insertion sort روی ورودیِ تصادفی: مقایسه")
table([(n, insertion_sort(shuffled[n])[1]) for n in LADDER], "مقایسه", ",d")
print("\n— insertion sort روی ورودیِ تصادفی: جابه‌جایی")
table([(n, insertion_sort(shuffled[n])[2]) for n in LADDER], "جابه‌جایی", ",d")
```

```text
— insertion sort روی ورودیِ تصادفی: مقایسه
         n            مقایسه     نسبت به سطر قبل
       250            14,113                   —
       500            65,356                4.63
     1,000           253,743                3.88
     2,000         1,022,176                4.03

— insertion sort روی ورودیِ تصادفی: جابه‌جایی
         n         جابه‌جایی     نسبت به سطر قبل
       250            13,868                   —
       500            64,865                4.68
     1,000           252,749                3.90
     2,000         1,020,183                4.04
```

<div dir="rtl">

**روی ورودیِ تصادفی، `insertion sort` هم `4` می‌دهد — `O(n²)`.** مقایسه‌هایش حدودِ نصفِ `selection sort` است (`1,022,176` در برابرِ `1,999,000`)، ولی **جابه‌جایی‌هایش بیش از پانصد برابر بیشتر است**: `1,020,183` در برابرِ `1,989`. **دقیقاً معاملهٔ برعکس.**

> 🤔 **اول حدس بزن:** حالا همان دو الگوریتم را روی فهرستی می‌بریم که **از قبل مرتب است**. برای هرکدام یک عدد در ستونِ نسبت بنویس.

</div>

```python
already = {n: sorted(shuffled[n]) for n in LADDER}
reverse = {n: sorted(shuffled[n], reverse=True) for n in LADDER}
print("— insertion sort روی ورودیِ از پیش مرتب")
table([(n, insertion_sort(already[n])[1]) for n in LADDER], "مقایسه", ",d")
print("\n— insertion sort روی ورودیِ وارونه")
table([(n, insertion_sort(reverse[n])[1]) for n in LADDER], "مقایسه", ",d")
print("\n— selection sort روی همان ورودیِ از پیش مرتب")
table([(n, selection_sort(already[n])[1]) for n in LADDER], "مقایسه", ",d")
```

```text
— insertion sort روی ورودیِ از پیش مرتب
         n            مقایسه     نسبت به سطر قبل
       250               249                   —
       500               499                2.00
     1,000               999                2.00
     2,000             1,999                2.00

— insertion sort روی ورودیِ وارونه
         n            مقایسه     نسبت به سطر قبل
       250            31,125                   —
       500           124,750                4.01
     1,000           499,500                4.00
     2,000         1,999,000                4.00

— selection sort روی همان ورودیِ از پیش مرتب
         n            مقایسه     نسبت به سطر قبل
       250            31,125                   —
       500           124,750                4.01
     1,000           499,500                4.00
     2,000         1,999,000                4.00
```

<div dir="rtl">

**سه جدول، و کلِ حرفِ این فصل در فاصلهٔ سطرِ آخرشان است.**

- روی ورودیِ مرتب، `insertion sort` در `n = 2,000` فقط **`1,999`** مقایسه می‌کند و ستونِ نسبتش `2.00` است. **یعنی `O(n)`** — چون برای هر عضو، همان مقایسهٔ اول جواب می‌دهد و حلقهٔ داخلی هرگز نمی‌چرخد.
- روی ورودیِ وارونه، همان تابع به **`1,999,000`** می‌رسد. **هزار برابرِ حالتِ قبل، با همان کد و همان تعدادِ عضو.**
- و `selection sort` روی ورودیِ مرتب هم دقیقاً `1,999,000` می‌کند — **مو نمی‌زند.**

**پس «`O(n²)` بودن» دربارهٔ این دو الگوریتم دو چیزِ متفاوت می‌گوید.** برای `selection sort` یک واقعیت است؛ برای `insertion sort` فقط بدترین حالت است، و **حالتی که واقعاً داری می‌تواند خطی باشد.** این همان تفکیکی است که ترمِ ۳ فصلِ ۴ برای `hash table` ساخت، و فصلِ ۸ نشان می‌دهد که `sorted` واقعی دقیقاً از همین خاصیت سوءاستفاده می‌کند.

> ✅ **چک کن:** فهرستی بساز که فقط **دو** عضوش جابه‌جا باشند — مثلاً `sorted(shuffled[1_000])` را بگیر و دو عضوِ کنارِ هم را عوض کن. مقایسه‌های `insertion sort` باید نزدیکِ `1,000` بماند، نه چیزی نزدیکِ نیم‌میلیون. **اگر عددِ بزرگ گرفتی، احتمالاً به‌جای دو همسایه، عضوِ اول و آخر را جابه‌جا کرده‌ای** — و آن یکی واقعاً گران است.

## ۶. مقایسه‌ای که ممکن نیست

هر دو الگوریتمِ این فصل روی یک فرض ایستاده‌اند: **هر دو عضو را می‌شود با هم مقایسه کرد.** وقتی این فرض نباشد، هیچ‌کدام کار نمی‌کنند.

</div>

```python
mixed = [3, "10", 7]
try:
    insertion_sort(mixed)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: '<=' not supported between instances of 'int' and 'str'
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** پیام دقیقاً می‌گوید کجا گیر کرده: عملگرِ `<=` بینِ یک `int` و یک `str` تعریف نشده. **این خطا معمولاً از داده می‌آید، نه از کد** — یک فایل که بعضی سطرهایش عدد است و بعضی سطرهایش رشتهٔ عدد. راهِ حل این است که **قبل از مرتب‌سازی** نوع را یکدست کنی، نه اینکه سطرهای مشکل‌دار را دور بریزی. **و اگر مطمئنی همه عددند ولی باز این خطا را می‌گیری، یعنی مطمئن نبودی.**

## ۷. و حالا با ساعت

</div>

```python
print("— selection sort (زمان)")
table([(n, 1000 * clock(lambda v=shuffled[n]: selection_sort(v), repeat=2))
       for n in LADDER], "زمان (ms)", ",.1f")
print("\n— insertion sort روی ورودیِ تصادفی (زمان)")
table([(n, 1000 * clock(lambda v=shuffled[n]: insertion_sort(v), repeat=2))
       for n in LADDER], "زمان (ms)", ",.1f")
```

```text-approx
— selection sort (زمان)
         n         زمان (ms)     نسبت به سطر قبل
       250               1.4                   —
       500               6.2                4.53
     1,000              26.9                4.35
     2,000             108.8                4.05

— insertion sort روی ورودیِ تصادفی (زمان)
         n         زمان (ms)     نسبت به سطر قبل
       250               1.4                   —
       500               7.4                5.24
     1,000              26.4                3.54
     2,000             105.9                4.01
```

<div dir="rtl">

**ساعت همان `4` را می‌گوید، با همان لهجهٔ لرزانی که ترمِ ۱ فصلِ ۵ نشان داد.** و یک چیزِ دیگر هم می‌گوید: دو الگوریتمی که تعدادِ مقایسه‌شان دو برابر با هم فرق داشت، زمانشان تقریباً یکی درآمد — **چون `insertion sort` آن مقایسهٔ کمتر را با جابه‌جاییِ خیلی بیشتر پس داد.** دو ستونِ بخشِ ۳ تا ۵ دقیقاً همین را از قبل گفته بودند.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** دو الگوریتمِ مرتب‌سازی با جوابِ تأییدشدهٔ برابر، هرکدام روی سه نوع ورودی: تصادفی، از پیش مرتب، و وارونه. **در کدام بازهٔ `n`؟** ۲۵۰ تا ۲٬۰۰۰ — بازه‌ای که در آن پایتونِ خالص با دو میلیون مقایسه در حدودِ یک دهمِ ثانیه تمام می‌کند. **با چند تکرار، و کمینه یا میانگین؟** جدول‌های شمارش یک اجرا و قطعی؛ جدولِ زمان دو تکرار به‌علاوهٔ گرم‌کننده، کمینه.

> 🤖 **از دستیارت بپرس:** «چرا `selection sort` روی ورودیِ از پیش مرتب هیچ سریع‌تر نمی‌شود؟» بعد این را هم بپرس: **«کدام‌یک از این دو الگوریتم برای مرتب کردنِ رکوردهای خیلی بزرگ بهتر است و چرا؟»** — جوابِ درست باید به تعدادِ **جابه‌جایی** برسد، نه به تعدادِ مقایسه. اگر دستیارت فقط گفت «هر دو `O(n²)` هستند و فرقی نمی‌کنند»، **جدولِ جابه‌جاییِ بخشِ ۴ و ۵ را جلویش بگذار.**

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `selection sort` | سلکشن سورت | در هر پاس کوچک‌ترینِ باقی‌مانده را به جای درستش می‌برد |
| `insertion sort` | اینسرشن سورت | هر عضو را در جای درستش بینِ عضوهای مرتبِ قبلی می‌نشاند |
| loop invariant | لوپ اینوَریِنت | جمله‌ای که قبل و بعد از هر دورِ حلقه درست می‌ماند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا تعدادِ مقایسه و تعدادِ جابه‌جایی را جدا شمردیم؟

**تمرینِ اجباری:** `bubble sort` را بنویس — همسایه‌های ناجور را جابه‌جا کن و آن‌قدر پاس بزن تا هیچ جابه‌جایی‌ای لازم نشود. **هر دو شمارنده را داشته باش** و جدولِ چهار اندازه‌ای‌اش را روی ورودیِ تصادفی و ورودیِ از پیش مرتب بگیر. **سؤالِ اصلی: روی ورودیِ مرتب به `insertion sort` شبیه‌تر است یا به `selection sort`، و چرا؟** جوابت باید بگوید کدام خط از کدت باعثِ این شباهت می‌شود.

**تمرینِ ستاره‌دار ⭐:** فهرستی از `n` عضو بساز که در آن `insertion sort` **دقیقاً** `n - 1` مقایسه بکند، و فهرستی دیگر که در آن دقیقاً `n(n-1)/2` مقایسه بکند. **قبل از اجرا پیش‌بینی کن** هر دو عدد در `n = 1,000` چند می‌شوند، بعد اجرا کن و خطای پیش‌بینی‌ات را بنویس. حالا سؤالِ سخت: **فهرستی بساز که عددش دقیقاً وسطِ این دو بیفتد** و بگو چطور ساختی‌اش.

## در فصل بعد

هر دو الگوریتمِ این فصل یک اشکالِ مشترک دارند: **در هر پاس، فقط یک عضو را سرِ جایش می‌گذارند.** برای `n` عضو یعنی `n` پاس، و هر پاس هم به `n` نگاه می‌کند — همان‌جا `n²` متولد می‌شود.

فصلِ بعد ایدهٔ کاملاً متفاوتی می‌آورد: **فهرست را نصف کن، هر نصف را مرتب کن، دو نصفِ مرتب را به هم بچسبان.** نتیجه‌اش این است که در `n = 8,000` به‌جای میلیون‌ها مقایسه، فقط **`93,704`** مقایسه لازم می‌شود و ستونِ نسبت از `4.00` به **`2.19`** می‌افتد. **و آن‌جا هم می‌شماریم که این سرعت با چه حافظه‌ای خریده شده.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t4/s03-quadratic-sorts (یادستان, Yaadestan)
