CodePlexProject Hosting for Open Source Software

TimSort is relatively new sorting algorithm invented by Tim Peters in 2002, which is a hybrid of adaptive MergeSort and InsertionSort. It is not worse than QuickSort which modified version is used as default sorting algorithm in .NET. TimSort's average case performance is O(n log n) (same as QuickSort) but both best case and worst case performances are bettern then QuickSort: O(n) and O(n log n) respectively (QuickSort is O(n log n) and O(n^2)).

Wikipedia:

http://en.wikipedia.org/wiki/Timsort

Josh Bloch's Java implementation:

http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/TimSort.java?view=co

TimSort takes advantage of two facts:

- data we sort is often already partially sorted
- comparison might be expensive (complex Compare method) while swapping elements is cheap (swapping pointers)

- Random data
- Builtin: 1859.4927ms
- TimSort: 1773.2582ms

- Generally ascending data (80% chance that next item is greater than previous one)
- Builtin: 1166.6400ms;
- TimSort: 247.1780ms

- Generally descending data (80% chance that next item is smaller than previous one)
- Builtin: 1190.5521ms
- TimSort: 571.7132ms

- Random data
- Builtin: 6117.1032ms
- TimSort: 4578.1129ms

- Generally ascending data (80% chance that next item is greater than previous one)
- Builtin: 5323.7977ms
- TimSort: 841.0910ms

- Generally descending data (80% chance that next item is smaller than previous one)
- Builtin: 5321.9103ms
- TimSort: 1094.5267ms

Last edited May 5, 2012 at 12:18 AM by Krashan, version 12