[llvm-dev] code to sort otherwise-unsortable "ilist"s, e.g. symbol tables

[Abe Skolnik via llvm-dev]

On 08/18/2016 10:23 AM, Duncan P. N. Exon Smith wrote:

> IMO list sorts should be:
> - O(n lg n) complexity.
> - Stable.

> I haven't looked carefully enough at this to be sure it meets these criteria.  Does it?

Stable if I did it right, but not O( n ⋅ log₂(n) ): insertion sort.  For reference: 
https://en.wikipedia.org/wiki/Insertion_sort

Also, I found this helpful-seeming web site while searching for the Wikipedia links:

   http://bigocheatsheet.com/


> It's possible the current in-tree one doesn't either

Maybe.  It uses a merge sort, which should be O( n ⋅ log₂(n) ), and _can_ be stable.  Quoting 
<https://en.wikipedia.org/wiki/Merge_sort>: "Most implementations produce a stable sort"


> if we're going to fix it let's *fix* it.

I _like_ that attitude.  ;-)


> I'm also not convinced this is the right direction; using a single list makes it complicated.

No _kidding_! ;-)  It took a _lot_ of work to get intra-list sorting [1] working, [2] rewritten 
almost from scratch so it could quickly-enough handle a >7000-GV translation unit without 
seeming like it`s stuck while sorting even with a fast CPU doing the compilation.


> My inclination is to split out lower-level merge/sort operations that avoid the calls to transferNodesToList, as I mentioned before

If you can fix the already-in-tree code so that the existing merge-sort code will work on 
"iplist"s not only without crashing, but also _correctly_, then I`m all for it.  I don`t care 
much whether or not the code I recently emailed makes it into the tree.  I wrote it for a 
purpose, and that purpose now seems dead, so "that`s life" -- sometimes we write code just so 
that, in the end, we can throw it away.  I`ve been programming for enough years that I already 
knew that before I started working on this.  It was good practice and I probably learned something.

Regards,

Abe