Mergesort (ترتيب الدمج)
الاستراتيجية
تعتمد على مبدأ "فرق تسد".
1. اقسم المصفوفة إلى نصفين.
2. رتب كل نصف (بشكل عودي Recursive).
3. ادمج (Merge) النصفين المرتبين في مصفوفة واحدة.
- الوقت: $O(N \log N)$ في جميع الحالات (الأفضل والأسوأ).
- المساحة: $O(N)$ (يحتاج مصفوفة إضافية للدمج). وهذا هو عيبه الوحيد.
Merge Step
Quicksort (الترتيب السريع)
الأسرع عملياً (Practically Fastest)
أيضاً "فرق تسد"، لكن التقسيم هنا ليس بالنصف، بل بناءً على قيمة محددة تسمى المحور (Pivot).
- العناصر الأصغر من Pivot تذهب لليسار.
- العناصر الأكبر تذهب لليمين.
- إذا اخترت أول عنصر وكان المصفوفة مرتبة، يصبح الأداء $O(N^2)$ (كارثة!).
- أفضل استراتيجية: Median-of-Three (اختر الأول، الأخير، والوسط، وخذ وسيطهم) .
External Sorting (ترتيب الملفات)
المشكلة
ماذا لو كانت البيانات أكبر من الذاكرة (RAM)؟ (مثلاً 10GB بيانات في 2GB رام).
لا يمكننا استخدام Quicksort لأنه يتطلب وصولاً عشوائياً (Random Access)، والقرص بطيء جداً في ذلك.
الحل: K-Way Merge Sort
- اقرأ جزءاً بحجم الذاكرة (Chunk).
- رتبه في الذاكرة واحفظه كملف مؤقت (Run).
- كرر حتى تنتهي البيانات.
- ادمج الملفات المؤقتة معاً (Merge Pass).
Tape Drives Logic
نستخدم أشرطة (أو ملفات) لأننا نقرأها بالتسلسل (Sequentially) فقط، وهو ما يبرع فيه الـ Merge Sort.
Quicksort Complexity
Average: $O(N \log N)$.
Worst Case: $O(N^2)$ (يحدث إذا كان الـ Pivot سيئاً جداً، مثل اختيار أصغر عنصر دائماً).
على عكس Mergesort الذي يضمن $O(N \log N)$ دائماً.
Memory Usage
Mergesort: $O(N)$ (يحتاج مصفوفة إضافية).
Quicksort: $O(\log N)$ (للمكدس في الاستدعاء العودي).
Heapsort: $O(1)$ (In-place).
لذلك Quicksort هو المفضل في الذاكرة (In-place تقريباً) وأسرع بسبب الكاش.