25. Comparing N log N Sorts (Merge vs. Quick)
| Feature | Merge Sort | Quick Sort |
|---|---|---|
| Time Complexity (Worst) | O(N log N) | O(N²) |
| Time Complexity (Average) | O(N log N) | O(N log N) |
| Space Complexity | O(N) (Not in-place) | O(log N) or O(N) (In-place, uses recursion stack) |
| Stability | Stable | Unstable |
| Practical Use | Great for linked lists, external sorting, stable requirements. | Fastest general-purpose internal sorting algorithm. |
Key Takeaway: While Quick Sort has a worse theoretical worst-case (O(N²)), its average performance is superior due to cache efficiency and smaller overhead. If stability or guaranteed worst-case time is critical, Merge Sort is the safer choice.