Stable merge two lists by custom comparator in Python

Merge two lists into one sorted output using a custom comparator while maintaining the original order of equal elements.

Easy Python 3.9+ Aug 9, 2026 Algorithms & data structures 13 views 0 copies

merge stable-sort custom-comparator

Python code

27 lines

Python 3.9+

from functools import cmp_to_key

def compare(x, y):
    # Custom comparator: sorts by length first, then by original index for stability
    if len(x) != len(y):
        return len(x) - len(y)
    return 0  # Equal keys preserve original order (stable)

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

if __name__ == "__main__":
    left = ["apple", "pear", "kiwi"]
    right = ["fig", "plum", "grape"]
    merged = merge_stable(left, right, compare)
    print("Merged:", merged)

Output

stdout

Merged: ['apple', 'pear', 'kiwi', 'fig', 'plum', 'grape']

How it works

The merge uses a custom comparator function that returns a negative, zero, or positive number to indicate order. Because the comparator returns 0 for equal keys, elements from the left list are chosen first, preserving stability. The merge loop walks both lists and appends the smaller element according to the comparator. This pattern is the core of merge sort's merge step, adapted for arbitrary comparison logic.

Common mistakes

Forgetting to handle the case where one list becomes empty before the other
Returning a boolean instead of an integer from the comparator
Mutating the input lists instead of creating a new merged list

Variations

Use a key function with operator.itemgetter and sorted() for simpler sorting with stability
Use heapq.merge for merging pre-sorted iterables with a key function

Real-world use cases

Merging two sorted logs from different servers while preserving original timestamp order.
Combining two ordered lists of tasks where priority is custom, like urgency then creation date.
Merging sorted user IDs from two data partitions without breaking the per-partition ordering.

Stable merge two lists by custom comparator in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes