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]

2 comments:

  1. Simple and effective comparison, many thanks.

    ReplyDelete
  2. Quicksort is slightly sensitive to input that happens to be in the right order, in which case it can skip some swaps. Mergesort doesn't have any such optimizations, which also makes Quicksort a bit faster compared to Mergesort.

    Below link can be useful to find out the more difference and to know more about quicksort and mergesort

    Why Quick sort is better than Merge sort

    ReplyDelete