Timsort (Q942403)
Jump to navigation
Jump to search
hybrid sorting algorithm based on insertion sort and merge sort
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Timsort |
hybrid sorting algorithm based on insertion sort and merge sort |
Statements
2002
0 references
2002
0 references
2 references
[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best). (English)
24 February 2011
TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. (English)
0 references
0 references
1 reference