Quick sort vs Merge sort

Table of Contents

Here’s a concise comparison of Quick Sort vs. Merge Sort:

How it works: Picks a pivot (often the last element), partitions the array into elements smaller and larger than the pivot, then recursively sorts the partitions.
Time Complexity:
- Average: O(n log n)
- Worst: O(n²) (rare, e.g., when the array is already sorted and a bad pivot is chosen)
Space Complexity: O(log n) for recursive calls (in-place sorting).
Advantages:
- In-place sorting (minimal extra memory).
- Faster in practice due to cache efficiency and fewer memory operations.
- Good for most real-world datasets.
Disadvantages:
- Unstable (may reorder equal elements).
- Worst-case O(n²) performance with poor pivot choices (mitigated by random pivot or median-of-three).
Best for: General-purpose sorting, especially with smaller datasets or when memory is limited.

How it works: Divides the array into two halves, recursively sorts each half, then merges the sorted halves.
Time Complexity:
- Average/Worst/Best: O(n log n) (consistent performance).
Space Complexity: O(n) for temporary arrays during merging.
Advantages:
- Stable (preserves order of equal elements).
- Guaranteed O(n log n) performance, regardless of input.
- Works well for linked lists and external sorting (e.g., disk-based data).
Disadvantages:
- Requires O(n) extra space.
- Slower in practice than Quick Sort due to more memory operations.
Best for: Large datasets, linked lists, or when stability is required.

Quick Sort: Choose for general-purpose sorting, especially when memory is constrained or cache efficiency matters.
Merge Sort: Choose for stable sorting, linked lists, or when guaranteed O(n log n) is critical (e.g., large datasets or external sorting).