Merging sorted data structures is a fundamental algorithmic pattern that appears throughout computer science. The core idea is to combine two or more already-sorted collections into a single sorted collection efficiently.
The key insight behind merge operations is that when both input collections are sorted, you can create the final sorted result by making local decisions. You don't need to see all the data at once – you can compare just the "front" elements of each collection and choose the smaller one.
This approach works because of a crucial property: if both collections are sorted, then the smallest remaining element in the merged result must be either the first element of collection A or the first element of collection B. There's no need to look ahead or backtrack.
The algorithm follows a simple pattern:
For linked lists specifically, this pattern becomes even more elegant because you're not copying data – you're just rearranging pointers. Instead of creating new nodes, you redirect the next pointers to weave the existing nodes into the correct order.
A common technique is to use a "dummy head" node. This eliminates special cases for handling the very first element of the result, making your code cleaner and less error-prone. The dummy node serves as a placeholder that you can discard at the end.
1def merge_sorted_arrays(arr1, arr2):
2 """Merge two sorted arrays into one sorted array."""
3 result = []
4 i = j = 0
5
6 # Compare elements from both arrays
7 while i < len(arr1) and j < len(arr2):
8 if arr1[i] <= arr2[j]:
9 result.append(arr1[i])
10 i += 1
11 else:
12 result.append(arr2[j])
13 j += 1
14
15 # Add remaining elements
16 result.extend(arr1[i:])
17 result.extend(arr2[j:])
18
19 return result