Merge arbitrary number of ordered lists via recursion + reduction

merge_ordered_lists.py

from functools import reduce


def merge(lst1, lst2):
    """Merges two sorted lists.
    >>> s1 = [1, 3, 5]
    >>> s2 = [2, 4, 6]
    >>> merge(s1, s2)
    [1, 2, 3, 4, 5, 6]
    >>> s1
    [1, 3, 5]
    >>> s2
    [2, 4, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    >>> merge([2, 3, 4], [2, 4, 6])
    [2, 2, 3, 4, 4, 6]
    """
    if not lst1 or not lst2:
        return lst1 + lst2

    if lst1[0] < lst2[0]:
        return [lst1[0]] + merge(lst1[1:], lst2)
    else:
        return [lst2[0]] + merge(lst1, lst2[1:])


def merge_k_lists(*args):
    """Merges arbitrary number of ordered lists.
    >>> s1 = [1, 3, 5]
    >>> s2 = [2, 4, 6]
    >>> s3 = [12, 14, 16]
    >>> s4 = [13, 15, 17]
    >>> s5 = [1, 10, 100, 1000]
    >>> merge_k_lists([], [2, 4, 6], [1, 2, 3])
    [1, 2, 2, 3, 4, 6]
    >>> merge_k_lists([1], [2], [3], [6, 28])
    [1, 2, 3, 6, 28]
    >>> merge_k_lists(s1, s2, s3, s4, s5)
    [1, 1, 2, 3, 4, 5, 6, 10, 12, 13, 14, 15, 16, 17, 100, 1000]
    >>> s1
    [1, 3, 5]
    >>> s4
    [13, 15, 17]
    >>> s5
    [1, 10, 100, 1000]
    """
    return reduce(lambda x, y: merge(x, y), args)