Sorting It Out - Thu, 16 Feb 2012

In my past life as a Computer Chess programmer, I became quite an expert in developing data structures, implementing algorithms and heuristics, and optimizing programs to the n’th degree. So doing something like sorting the events within a person in Behold shouldn’t have been much of a problem.

It’s very simple to do. Each event is one entry in a list. For that entry, I create a sort-key, made up of the type of event and the internal sortable date for the event. Then just call the TList.sort built-in procedure telling it to use the sort-key to sort, and voila! It’s sorted.

But just one little problem. If there are multiple birth (or death) events for an individual because different evidence said different things, then I want those events to be listed in the order they are given, not by date. The reason is that GEDCOM says these events should be entered in the order most-likely to least-likely, and therefore the order should be retained. That is not true for other events which can occur multiple times, but a birth or death event for an individual can only occur once.

So I do the TList.sort and I find that these multiple birth events are shown in a different order than what their order was in the GEDCOM. Whoops! What happened?

I research a bit more and I see that Delphi uses the QuickSort algorithm. It is what it says it is: “Quick”. But that algorithm has the unfortunate attribute of not being stable. That means it may change the relative order of records with equal keys. The birth events without the date (because I don’t want to sort them by date) do not have any difference in my sort key, and their order changes.

So the obvious first attempt at a solution is to simply switch to a stable sorting technique. A Merge Sort would be a good one. To my surprise, no other sort techniques were built into Delphi – just the QuickSort was. Looking for Delphi code on the web to do a Merge Sort came up with some possibilities, but they are much more complicated routines, and I thought there must be something simpler. If speed was the issue, I could switch my list to a linked-list, and then the Merge Sort would be blazingly fast. But I didn’t want to go changing data structures now. I just wanted the sort to work.

The simple answer, verified by my asking a question of StackOverflow, was to use the order of the event within the individual as part of the sort key. So that’s what I did. I added that order number to the end of all the sort keys. This worked like a charm.

It was nice to study some of the old sorting algorithms again. I don’t often get the chance anymore.