Front page | perl.perl5.porters |
Postings from July 2004
On Wed, 2004-06-30 at 08:11, Ton Hospel wrote: > Mergesort works well too if you cut off runs at M. > you start with N/M groups of M elements, each sort in O(MlogM), so that > gives (NlogM). > Then you need to combine N/M runs, which is (N/M-1) combines, in which each > can stop after collecting M elements => O(N). > So the sum is still O(NlogM) > > And since the plain sort already is mergesort, i think that would be > the best choice since it will e.g. have the same stability properties, > and the partial sort smoothly extends to the full sort. Does not the combining involve more comparisons? -- david nicol this message was sent from a filtering e-mail address. Until I add you to my friends list, to get by Big Emet the cowboy doorman your reply must include a listed "magic phrase" such as "cat and buttered toast"