Merge sort هو ترتيب divide-and-conquer، مستقر يعمل في وقت مضمون O(n log n). يقسم المصفوفة إلى نصين، يرتب كل نصف بشكل متكرر، ثم يدمج النصين المرتبين.
عنصر واحد مرتب بالفعل (حالة الأساس). دمج قائمتين مرتبتين خطي، ونحن نقوم بـ log n مستويات من الدمج.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
مثالي عندما تحتاج إلى الاستقرار أو O(n log n) مضمون، وللقوائم المرتبطة والترتيب الخارجي للملفات الضخمة. الذاكرة الإضافية O(n) هي أساس عيبها الرئيسي.
Merge sort يضمن O(n log n) بغض النظر عن الإدخال، بخلاف quicksort's O(n²) الحالة الأسوأ.
استقراره يحافظ على الترتيب النسبي للمفاتيح المتساوية، وهو يهم للفرز متعدد المفاتيح.
خطوة الدمج هي primitive قابلة لإعادة الاستخدام، والهيكل divide-and-conquer هو قالب ستعيد استخدامه في كل مكان.
مكتبة من أسئلة مقابلات تقنية المعلومات مع إجابات مفصّلة — من المبتدئ إلى المتقدم.
تبرع