Saturday, October 3, 2009

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]

1 comment:

  1. Simple and effective comparison, many thanks.