On Mon, Apr 18, 2016 at 9:09 AM, Hans Petter Selasky <hps at selasky.org> wrote > I think the algorithm is switching to mergesort. I'll look up the paper > and add that correctly before commit. > No, it switches to insertion sort, assuming that it's acting on an already sorted array. If that assumption is wrong you still get O(n**2) complexity.