Merge Sort using iterators

merge.py

from heapq import merge


def merge_lr(left, right):
    """Merge left and right sequences."""

    result = []
    left_idx, right_idx = 0, 0
    while left_idx < len(left) and right_idx < len(right):
        # change the direction of this comparison to change the direction of the sort
        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1
 
    if left:
        result.extend(left[left_idx:])
    if right:
        result.extend(right[right_idx:])
    return result


def interleave(*segments):
    """Interleave segments."""
    
    # seed the vals with the first item from each segment
    vals = {
        segment: x for segment, x in (
            (segment, next(segment, None)) for segment in (
                # convert all iterables to iterators
                iter(segment) for segment in segments   
            )
        )
        # trim any empty segments
        if x is not None
    }

    # find the minimum remaining values from each segment and return
    while vals:
        m = min(vals.values())

        for segment, x in vals.items():
            if x == m:
                yield x

                # update the consumed value to next in segment
                try:
                    vals[segment] = next(segment)
                except StopIteration:
                    # remove segment when exhausted
                    vals.pop(segment)


def merge_sort(l, merger=interleave):
    """Merge Sort."""

    if len(l) <= 1:
        return l

    middle = len(l) / 2

    return(list(merger(
        merge_sort(l[:middle]),
        merge_sort(l[middle:])
    )))