/
Programming

# In-depth: Smoothsort vs. Timsort

In this reprinted #altdevblogaday in-depth piece, Crytek's technical lead Jaewon Jung examines Smoothsort and Timsort, offering benchmark results from his tests with the two sorting algorithms.
• Data size: 100,000
• Data type: int or double
• Unit: milliseconds
• Partially sorted #0: each subarray of size 10 in 100,000 sequence is sorted
• Partially sorted #1: each subarray of size 1000 in 100,000 sequence is sorted
• The original implementation of Keith's uses std:bitset. 'Smoothsort(raw bit)' is a modified one that uses raw bit operations instead
• Test hardware: Intel Core i7 920 / 6GB RAM
As you can see, both Timsort and Smoothsort didn't cut the mustard. Smoothsort is worse than STL sorts in all cases (even with std:bitset replaced with raw bit operations). Timsort shows a trade-off. In random or almost random sequences, not as good as STL ones, but in partially sorted sequences like 'Reversed', 'Sorted' and 'Partially sorted #1′, it shows impressive speed-up. Admittedly, apart from replacing an obvious culprit like std::bitset, I didn't try any thorough optimization for each. So if you can see/suggest any optimization opportunities for both that I missed, please leave a comment. std::sort/std::stable_sort I was somewhat impressed with STL sorters at this point and found out I hadn't known much about their internal implementations except the foggiest idea that it would be a variant of quick sort. So I digged into the source(STL in VS2012 RC, specifically). As you know, there are two, one which doesn't maintain the relative order of records with equal keys(unstable) and the other which keeps it(stable). std::sort is basically a quick sort with a median of medians algorithm to decide a partition pivot. Once the sequence becomes small enough(< 32), it switches to an insertion sort. Or if the recursion becomes too deep(> 1.5log2(N)), then it switches to a heap sort. std::stable_sort is not a quick sort. It's a sort(pun intended) of a merge sort. First, it insertion-sorts each chunk of size 32 and merge them hierarchically. Initially, it tries to get a temp storage of the half size of the original sequence and use it when merging. If the allocation fails, then it tries a smaller size, but this means more recursions and merges, so slower, of course. In the sense that it is a combo of merge sort and insertion sort, one can say it's similar to Timsort in essence, although the latter has much more complex tricks up its sleeve. Codes for std::sort/std::stable_sort are relatively easy to follow(especially in comparison with understanding Smoothsort or Timsort), so I strongly recommend to take stock of them, if you haven't done before. Conclusion
• Asymptotic performance is not a whole story at all. The constant factor matters (an obvious thing, but still worth repeating)
• Timsort can be a viable alternative when data are not so random
• Smoothsort, though mathematically clever, doesn't cut the mustard
• std::sort/std::stable_sort is pretty good in most of the cases
• For small data, insertion sort is very good. So it's a good strategy to mix it with other algorithms to devise a good hybrid sorting algorithm
References [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]

### Latest Jobs

#### Sucker Punch Productions

Bellevue, Washington
08.27.21
Combat Designer

#### Xbox Graphics

Redmond, Washington
08.27.21
Senior Software Engineer: GPU Compilers

#### Insomniac Games

Burbank, California
08.27.21
Systems Designer

#### Deep Silver Volition

Champaign, Illinois
08.27.21
Senior Environment Artist
More JobsÂ Â Â