Teaching Kids Programming - Merging Two Sorted List | Algorithms, Blockchain and Cloud

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two sorted list, if we want to merge it, we can do this optimally using two pointers in O(N+M) where N and M are the sizes of the two sorted lists respectively.

Append and Re-sort

We can, however, append one list to another and re-sort the entire list, this costs O((N+M)Log(N+M)).

def merge(a, b):
  c = a + b
  c.sort()
  return c

def merge(a, b):
  c = a + b
  c.sort()
  return c

Merge Two Sorted Lists using Two Pointer

We can use two pointers to point to the current smallest element, then compare both, move forward the smaller one. Continue until both points reach the their end.

def merge(a, b):
    i, j, la, lb = 0, 0, len(a), len(b)
    res = []
    while i < la and j < lb:
        if a[i] < b[j]:
            res += [a[i]]
            i += 1
        else:
            res += [b[j]]
            j += 1
    while i < la:
        res += [a[i]]
        i += 1
    while j < lb:
        res += [b[j]]
        j += 1
    return res

def merge(a, b):
    i, j, la, lb = 0, 0, len(a), len(b)
    res = []
    while i < la and j < lb:
        if a[i] < b[j]:
            res += [a[i]]
            i += 1
        else:
            res += [b[j]]
            j += 1
    while i < la:
        res += [a[i]]
        i += 1
    while j < lb:
        res += [b[j]]
        j += 1
    return res

The runtime is O(N+M). The merged list takes O(N+M) space, if we do care.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

315 words
Last Post: A Simple Atbash Cipher Implementation
Next Post: Algorithms to Determine a Ugly Number/Integer

The Permanent URL is: Teaching Kids Programming – Merging Two Sorted List

Append and Re-sort

Merge Two Sorted Lists using Two Pointer

Related posts:

Leave a Reply