def msort(xs, lo=None, hi=None): if lo is None: lo = 0 hi = len(xs) if hi-lo < 2: return mid = lo + (hi-lo) // 2 msort(xs, lo, mid) msort(xs, mid, hi) merge(xs, lo, mid, hi) def msort(xs): s = [[0, len(xs) // 2, len(xs), "step 1"]] while s: lo, mid, hi, step = xs[-1] if step == "step 1": if hi-lo < 2: s.pop() else: s[-1][3] = "step 2" s.append([lo, lo + (mid-lo) // 2, mid, "step 1"]) elif step == "step 2": s[-1][3] = "step 3" s.append([mid, mid + (hi-mid) // 2, hi, "step 1"]) else: s.pop() merge(xs, lo, mid, hi)
