In article <1089335013.1041.182.camel@plaza.davidnicol.com>, david nicol <davidnicol@pay2send.com> writes: > Does not the combining involve more comparisons? Sure, but I accounted for them. N/M combines each collecting M elements from 2 runs of M => M compares per combine => O(N) compares, which then gets subsumed in the O(N log M) we already had from the first step