Merge two simple sorted lists
Input
merge_sorted([1, 3, 5], [2, 4])
Output
[1, 2, 3, 4, 5]
Interleave elements from both lists by comparing current elements. Resulting list stays sorted.
Full lesson preview
Merge Two Sorted Arrays as the Merge Step
Combine two sorted lists into one sorted list in linear time.
Python practice8 minSearching & SortingBeginnerLast updated March 25, 2026
Problem statement
Given two lists of numbers that are sorted in non-decreasing (ascending) order, merge them into a single list that remains sorted in non-decreasing order. The merged list should contain all elements from both input lists, preserving duplicates. Aim for O(n + m) time and O(n + m) additional space, where n and m are the lengths of the input lists.
Task
Write a function that merges two ascending-sorted lists into a single ascending-sorted list without using built-in sorting.
Examples
Input format
Two Python lists of numbers: merge_sorted(list1, list2)
Output format
A single Python list containing all elements from both inputs in ascending order.
Constraints
Both input lists are sorted in non-decreasing order. Do not use sorted() on the concatenation of the lists. Aim for linear time O(n + m).
Samples
Sample 1
Input
merge_sorted([1,2],[3,4])
Output
[1, 2, 3, 4]
Concatenate in sorted order by comparing heads of each input list.