21. فرز الدمج (Merge Sort): منهجية القسِّم تسُد (الجزء 1)
Merge Sort هي أول خوارزمية O(N log N) نغطيها، وهي تمثل قفزة كبيرة في الكفاءة للبيانات الكبيرة.
النموذج: القسِّم تسُد (Divide and Conquer)
Merge Sort مثال كلاسيكي لنموذج القسِّم تسُد (Divide and Conquer):
- القسِّم (Divide): تقسيم المشكلة (القائمة) إلى مشكلتين فرعيتين أصغر أو أكثر (قوائم فرعية) بشكل عودي.
- تسُد (Conquer): حل المشكلات الفرعية بشكل عودي. إذا كانت القائمة الفرعية صغيرة بما فيه الكفاية (مثل الحجم 0 أو 1)، فإن المشكلة تكون تافهة.
- الجمع (Combine/Merge): دمج حلول المشكلات الفرعية لحل المشكلة الأصلية.
خطوات Merge Sort
- التقسيم: تقسيم المصفوفة باستمرار إلى نصفين حتى يكون لديك N قوائم فرعية، تحتوي كل منها على عنصر واحد.
- الدمج (الجزء الصعب): دمج القوائم الفرعية بشكل متكرر لإنتاج قوائم فرعية مفرزة جديدة حتى تتبقى قائمة واحدة مفرزة فقط.