sort should ensure ordering of individual parents (also, mutation parents?)

[petrelharp]

sort( ) should produce valid tables; with #1192 one of the requirements not ensured by sort is that parent individuals come before children. We should do this! Also, I think we should do the same for mutations. (I'm only proposing sorting so that mutations who have their parent mutations specified get sorted correctly; otherwise we'd have to compute the mutation parents.)

Since sort is a bottleneck in forwards sims, and this sortedness is not required by simplify, perhaps this should be optional. (although it sounds annoying to make it optional)

[jeromekelleher]

Agreed. But:

Since sort is a bottleneck in forwards sims, and this sortedness is not required by simplify, perhaps this should be optional. (although it sounds annoying to make it optional)

I think edge sorting is the bottleneck, right? All the rest is pretty small fry compared to the large edge tables, so adding a few constant factors isn't going to make any difference. I would vote for doing it the way we think is right first, and then backing out an making it optional if it turns out to add to sort-time in forward sims.

[benjeffery]

I'm going to have a stab at this, @jeromekelleher and I just talked it over and sorting individuals is equivalent to topologically sorting the directed graph of parent references. Kahn's algorithm looks promising for this, it also will detect cycles in the graph.