Merge Sorted Sources

When To Use

Use this when consuming two sorted arrays, lists, or interval streams.

Template

i = 0
j = 0
 
while i < n and j < m:
    if a[i] should come first:
        take a[i]
        i++
    else:
        take b[j]
        j++
 
take leftovers

Problems

Merge Sorted Array

Problem: merge two sorted arrays into one sorted array.

Pattern: usually fill from the back to avoid overwriting nums1.

Applied pseudocode:

i = m - 1
j = n - 1
write = m + n - 1
 
while j >= 0:
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[write] = nums1[i]
        i--
    else:
        nums1[write] = nums2[j]
        j--
 
    write--

Merge Two Sorted Lists

Problem: merge two sorted linked lists.

Pattern: repeatedly attach the smaller current node.

Interval List Intersections

Problem: find intersections between two sorted interval lists.

Pattern: compare current intervals, then advance the one that ends first.