One of idea is add sorting of Datums to be splitted by cost of insertion. It's implemented in intarray/tsearch GiST indexes.
Yes, it's a good compromise between linear and quadratic entries distribution algorithms. In quadratic algorithm each time entry with maximal difference of inserion cost is inserted. Quadratic algorithm runs slowly than sorting one, but on my tests it shows slightly better results.
