Comparison between timsort and quicksort

algorithm sorting quicksort timsort
chenglou picture chenglou · Oct 14, 2011 · Viewed 28.7k times · Source

Why is it that I mostly hear about Quicksort being the fastest overall sorting algorithm when Timsort (according to wikipedia) seems to perform much better? Google didn't seem to turn up any kind of comparison.

Answer

Chang picture Chang · Oct 25, 2013

TimSort is highly optimization mergesort, it is stable and faster than old mergesort.

when comparing with quicksort, it has two advantages:

  1. It is unbelievably fast for nearly sorted data sequence (including reverse sorted data);
  2. The worst case is still O(N*LOG(N)).

To be honest, I don't think #1 is a advantage, but it did impress me.

Here are QuickSort's advantages

  1. QuickSort is very very simple, even a highly tuned implementation, we can write down its pseduo codes within 20 lines;
  2. QuickSort is fastest in most cases;
  3. The memory consumption is LOG(N).

Currently, Java 7 SDK implements timsort and a new quicksort variant: i.e. Dual Pivot QuickSort.

If you need stable sort, try timsort, otherwise start with quicksort.

Related questions

Quicksort with Python

I am totally new to python and I am trying to implement quicksort in it. Could someone please help me complete my code? I do not know how to concatenate the three arrays and printing them. def sort(array=[12,4,5,6,7,3,1,15]): less = [] …

Read More
Why is quicksort better than mergesort?

I was asked this question during an interview. They're both O(nlogn) and yet most people use Quicksort instead of Mergesort. Why is that?

Read More
Quicksort: Choosing the pivot

When implementing Quicksort, one of the things you have to do is to choose a pivot. But when I look at pseudocode like the one below, it is not clear how I should choose the pivot. First element of list? …

Read More