Merge Two Ordered Runs

Practice Exercise Interview Easy Merge Sort

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement merge_ordered_runs(left, right). Both inputs are sorted in nondecreasing order. Return one sorted list containing every value from both inputs, including duplicates, without calling sorted on their concatenation.

Starter code

def merge_ordered_runs(left, right):
    pass

Test cases

interleaved-runs

{
  "args": [
    [
      1,
      4,
      7
    ],
    [
      2,
      3,
      8
    ]
  ]
}

Expected: [1,2,3,4,7,8]

duplicates

{
  "args": [
    [
      1,
      2,
      2
    ],
    [
      2,
      3
    ]
  ]
}

Expected: [1,2,2,2,3]

Wizard outline

Step 1: Preserve the nonempty ordered run
Return a copy of right when left is empty. An empty run contributes no values, so the other run is already the correctly ordered result.
Step 2: Merge active fronts and append remainders
Advance the pointer holding the smaller front value, then append the untouched tail. Once one run is exhausted, every remaining value in the other run is already at least as large as the merged prefix.

Footguns and prerequisites

Stopping when either run ends drops the remaining suffix of the other run.
Advancing both pointers after a strict comparison loses one unselected value.
arrays strings two pointers sliding window

Reviewed references

Python More on Lists

Prepared Interview Problems

Merge Intervals(opens in a new tab)
Merge Two Ordered Runs isolates the output is sorted and contains exactly the consumed prefixes; the two pointers identify the smallest unconsumed candidates. That focused state discipline is required when implementing merge intervals as a complete Interview Problem.
Sort an Array(opens in a new tab)
Merge Two Ordered Runs isolates the output is sorted and contains exactly the consumed prefixes; the two pointers identify the smallest unconsumed candidates. That focused state discipline is required when implementing sort an array as a complete Interview Problem.

Recommended approach and implementation

Two already ordered runs can be combined in one pass by selecting the smaller current front. The output is sorted and contains exactly the consumed prefixes; the two pointers identify the smallest unconsumed candidates.

Why it works: At each step the smaller pointed value is the smallest remaining value overall, so appending it preserves sorted order. When one input ends, appending the other suffix preserves order and includes every value exactly once.

def merge_ordered_runs(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged