Python: Sorting Algorithms Benchmarks Comparison

Benchmarks performance comparison between Python sorting algorithms: InsertionSort, SelectionSort, BubbleSort, MergeSort, QucikSort, TimSort.

[very_uniq_handle]

unfair comparison because timsort is the builtin python sort function which is implemented in C.

[davidjames]

A better test would be to implement all of the popular sorting algorithms in c and run benchmarks on them. That way it is a level playing field. I suspect counting sort will win for random data, especially if the range of values is restricted such as from 0 to 65535 (16 bit unsigned numbers). However in real life, we tend to sort strings a lot more than numbers, so a good sorting algorithm must work well on strings such as full names.

[davidjames]

If you are sorting integers within a reasonable range of values, why not just use counting sort? Also, you didn't test heapsort in this comparison. Something I have an interest in is to find out which sort algorithm performs very well in an almost sorted starting state and then write a routine to quickly put it in that state. For example, suppose we had 100, 000 random integers to sort. The 1st step would be to put them in an almost sorted state (such as partitioning them like Quicksort does), then use some algorithm that works very well on almost sorted data.

[danieldelizaur]

how can timsort be so fast? I tried it (not in python) and it is usually between merge and quick In random data. why's python's implementation different?

[akshatagrawal]

There is no single magic bullet, oh maybe except "Tim Sort".
😅😅😅