Explain the concept of Merge Sort and its advantages over Quick Sort.
Instruction: Describe how Merge Sort operates and discuss scenarios where it might be preferred over Quick Sort.
Updated
Official answer
Merge sort splits a sequence, sorts the parts and merges them by repeatedly selecting the smaller front element. Standard comparison-based merge sort takes O(n log n) time in the worst case. A stable merge takes the left item first when keys tie, preserving the original order of equal keys.
A conventional array implementation needs O(n) auxiliary storage. Linked-list variants can merge by relinking nodes. Merging sorted runs also fits external sorting, where sequential I/O is valuable.
Ordinary quicksort partitions around a pivot. It has expected O(n log n) time with appropriate randomization, but can take O(n²) in its worst case. Common in-place versions are not stable and often have good locality. Library implementations may use hybrids that limit this worst case; compare the actual implementation.
Prefer merge sort when stable ordering, predictable comparison bounds or run-based external processing matter. Both families can be parallelized. Neither an asymptotic bound nor parallelizability establishes a real-time deadline or makes one universally faster.