Merge Three Sorted Lists | Dataford Interview Questions

Meta Logistics Dispatch receives three delivery-ID lists that are already sorted in nondecreasing order. Implement a function that merges them into one sorted list containing every ID from all three inputs.

Formal Specification

Given three Python lists list1, list2, and list3, where each list contains integers sorted in nondecreasing order, return a new list containing all elements from the three input lists in nondecreasing order. Do not modify the input lists. Duplicate values must be preserved.

Aim for a solution that runs in linear time relative to the total number of elements and uses only constant auxiliary space beyond the returned list.

Constraints

0 <= len(list1), len(list2), len(list3) <= 10^5
0 <= len(list1) + len(list2) + len(list3)
-10^9 <= every input value <= 10^9
Each input list is sorted in nondecreasing order
Duplicate values must be preserved
Input lists must not be modified

Function Signature

def merge_sorted_lists(list1, list2, list3):

Your question is Merge Three Sorted Lists. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem