Hello,
I am very familiar with most of the sorting algorithms that are taught in first year university (as I just finished my first year in software engineering at the University of Waterloo). As such my current go-to sorting algorithms are insertion (on mostly pre-sorted data, or data where I get each element one at a time [like inputs from stdin]), merge (which I use for optimality), and heap (which I don't use too much because I happen to prefer merge :) ). Anyways, I hate writing code that is not optimal. That is why for example when I am doing Project Euler problems I always solve them for the most general case, as well as I can. Typically either insertion or merge sort are ideal, but I have just begun a project that will involve sorting an entire dictionary that may or may not be mostly pre-sorted. As such I was hoping for a more efficient algorithm. Since I expect the dictionary to be possibly pre-sorted, but possibly unsorted I looked into timsort and smoothsort. Since identifying runs sounds complicated I thought I would learn smoothsort. The issue is that the wiki explanation is quite complicated and confusing. I am wondering if anybody can explain smoothsort better and perhaps provide a pseudo-code implementation. Thank you.