مرتب سازی ادغامی (Merge Sort)
در «مرتب سازی ادغامی (Merge Sort)» آرایه را نصف نصف می بُریم. سپس تکه ها را ادغام می کنیم. همیشه مقدار کوچک تر جلو می آید. این روش «تقسیم و حل (Divide and Conquer)» است و بازگشتی انجام می شود.
ایده اصلی با مثال ساده
مثل چیدن برگه های نمره است. اول برگه ها را دو دسته کن. سپس هر دسته را دوباره نصف کن. در پایان، دو دسته مرتب را با مقایسه سرِ هر دسته، به ترتیب ادغام کن.
- نصف کن تا تک عنصره شود.
- دو نیمه مرتب را مقایسه و ادغام کن.
- ادغام را ادامه بده تا آرایه کامل شود.
نکته: «بازگشت (Recursion)» یعنی تابع خودش را صدا می زند تا مسئله کوچک تر شود.
پیاده سازی بازگشتی در پایتون
در این نسخه، آرایه را می بُریم، دو نیمه را جداگانه مرتب می کنیم، سپس ادغام می کنیم.
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
leftHalf = arr[:mid]
rightHalf = arr[mid:]
sortedLeft = mergeSort(leftHalf)
sortedRight = mergeSort(rightHalf)
return merge(sortedLeft, sortedRight)
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
mysortedlist = mergeSort(mylist)
print("Sorted array:", mysortedlist)
نسخه بدون بازگشت (Bottom-Up)
اینجا به جای بازگشت، با اندازه زیرآرایه کوچک شروع می کنیم و دوبرابر می کنیم.
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def mergeSort(arr):
step = 1
length = len(arr)
while step < length:
for i in range(0, length, 2 * step):
left = arr[i:i + step]
right = arr[i + step:i + 2 * step]
merged = merge(left, right)
for j, val in enumerate(merged):
arr[i + j] = val
step *= 2
return arr
mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
mysortedlist = mergeSort(mylist)
print(mysortedlist)
گام های تمرینی سریع
- یک آرایه تصادفی بساز.
- تابع mergeSort را اجرا کن.
- نتیجه را با sort خود پایتون مقایسه کن.
- اندازه آرایه را افزایش بده و زمان را بسنج.
پیچیدگی زمانی
پیچیدگی «مرتب سازی ادغامی» برابر O(n \cdot \log n) است. چون همیشه می بُرد و همیشه ادغام می کند. بنابراین روی ورودی های مختلف تقریباً رفتاری یکنواخت دارد.
جمع بندی سریع
- مرتب سازی ادغامی پایدار و قابل اعتماد است.
- تقسیم و حل با ادغامِ مرتب انجام می شود.
- پیچیدگی زمانی: O(n·log n).
- برای درک تفاوت ها، ببین: مرتب سازی رادیکس و مرتب سازی شمارشی و مرتب سازی سریع.