Source code for tryalgo.merge_ordered_lists

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Merge two ordered lists
jill-jênn vie et christoph dürr - 2014-2019
"""


# snip{
[docs]def merge(x, y): """Merge two ordered lists :param x: :param y: x, y are nondecreasing ordered lists :returns: union of x and y in order :complexity: linear """ z = [] i = 0 j = 0 while i < len(x) or j < len(y): if j == len(y) or i < len(x) and x[i] <= y[j]: # priority on x z.append(x[i]) i += 1 else: z.append(y[j]) # now switch to y j += 1 return z
# snip}