Friday, June 22, 2012

Merge Sort vs Quick Sort

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

No comments:

Post a Comment