Merge Sort vs. Quick Sort: Overview

Merge Sort vs. Quick Sort: Overview
Merge Sort
Quick Sort
Time complexity (Average): O(n log n) Time complexity (Average): O(n log n)
Time complexity (Worst): O(n log n) Time complexity (Worst): O(n^2)
(Occurs when list is sorted)
Stable sort

Not dependent on any factors
Average case = Worst Case Not a stable sort

Dependent on randomness of list
Memory: O(n)
Additional memory space required Memory: O(log n)
Memory Complexity (Best): O(1)
Little additional memory space required

When to use Merge Sort? When additional memory usage is not a problem and list could be partial sorted


When to use Quick Sort? When additonal memory usage is a problem and the list is randomized.

[Source: Sorting Algorithm]