A very simple programming problem gave me the idea to look what modern search algorithm is the best. At the moment, I know and have used only merge sort and insertion sort. But I have never tried to compare their performance in different cases (different list lengths, different data, etc.).
After several minutes of search, I found that the insertion sort performs better on small array while merge soft performs better on large arrays and is theoretically better. It takes O(n*ln(n)) time comparing to O(n^2) time for the insertion cost. BUT! Python introduced TimSort in 2002 and have been using it since. As I understood, Android uses it since API Level 5 and a discussion about Java sort algorithm started in 2009 leaded to Java using TimSort now too.
From Wikipedia I understood that Timsort (invented by Tim Tim's_Lastname but described in some paper in 1990s) is an adaptive search algorithm that uses the idea that real world data is usually not random but partially sorted. Thus, it explores different data features and adapt to them. It achieves O(ln(n)) result on partially sorted data and is only 1.5% slower that optimized merge sort on the completely random data.
To be continued....
After several minutes of search, I found that the insertion sort performs better on small array while merge soft performs better on large arrays and is theoretically better. It takes O(n*ln(n)) time comparing to O(n^2) time for the insertion cost. BUT! Python introduced TimSort in 2002 and have been using it since. As I understood, Android uses it since API Level 5 and a discussion about Java sort algorithm started in 2009 leaded to Java using TimSort now too.
From Wikipedia I understood that Timsort (invented by Tim Tim's_Lastname but described in some paper in 1990s) is an adaptive search algorithm that uses the idea that real world data is usually not random but partially sorted. Thus, it explores different data features and adapt to them. It achieves O(ln(n)) result on partially sorted data and is only 1.5% slower that optimized merge sort on the completely random data.
To be continued....
No comments:
Post a Comment