algorithmsortingquicksorttimsort

Comparison between timsort and quicksort

Why is it that I mostly hear about Quicksort being the fastest overall sorting algorithm when, according to Wikipedia, Timsort seems to perform much better?

Solution

  • TimSort is a highly optimized 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.