Another method for sorting the census data for redistricting has occurred to me. Back in ancient times, there were machines that could sort punch cards. See: http://en.wikipedia.org/wiki/IBM_80_series_Card_Sorters. For example, cards could be sorted into ranges of latitude. The cards would be conveyed horizontally until they dropped into the proper bin below. Today, the same sort of thing can be done in software, known as a radix sort. This could be faster than even the merge sort that I was considering, and the code could be more compact as well. I hadn’t considered radix sort seriously before, since potentially a huge memory would be required. I remember monolithic 2K byte chips, so half gigabyte memories are huge to me. Ancient FORTRAN required arrays to be dimensioned at the beginning of the software program. Today, modern FORTRAN allows calculating efficient dimensions for the array before allocating memory to the array. The old way would have been to use a linear array and then calculate the 2 dimensional subscripts for that array.
I intend to write code for a radix type sort to separate the census blocks into stripes of latitude ranges. The census blocks in each stripe can then be sorted by longitude. Merge sort will hopefully work well enough for the stripes. Other methods of sorting may be faster, but I doubt it is worth my time to code them. After all, the goal is redistricting by computer. I have already learned way too much about sorting, but help is not on the way. I am still writing code and haven’t started debugging. A compile now and then reveals tons of errors that are easily fixed.
Decades ago, some academics tried computerized redistricting by growing districts from a seed. Sandboxwalls also grows districts from a seed. Even though that research was paid for by taxpayer dollars, that information is inaccessible, stuck up in ivory towers. I imagine those experiments mostly failed, as researchers after that pursued instead the heuristic methods for redistricting. Circles don’t fit together well, but I’m hoping my experiment with sandboxwalls will do better. Time will tell, but spare time is hard to come by. I envy the several contestant teams in the state of Virginia. Each team had over half a dozen undergraduates and a faculty advisor. The good news is that slowly more people are doing redistricting. Unfortunately, gerrymandering is still the clear winner.