Re: [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists

Am Donnerstag 31 Dezember 2009 11:38:51 schrieb Luke Palmer:

This cartesian product varies in its tail faster than its head, so every head gets its own unique tail.  If you reverse the order of the bindings so that it varies in its head faster, then tails are shared. If my quick and dirty reasoning is correct, it improves the space usage by a factor of the number of sublists.

That reasoning is supported by http://www.haskell.org/pipermail/haskell-cafe/2009-December/070184.html However, that concerns only the generation of the lists to be sorted, as far as I can see (that will be faster and use less memory). The main problem here is the space usage of the sorting, I think. For that, probably an external sort is the best solution.