An example test checks the cases you thought of. A property test states something that must hold for every input, an invariant, and checks it on hundreds of generated inputs. Libraries such as Hypothesis also shrink a failure to the smallest input. By hand, a seeded random.Random gets you most of the way, and the seed makes any failure repeatable.

import random

def dedupe(items):
    return list(dict.fromkeys(items))

rng = random.Random(7)
for _ in range(300):
    n = rng.randint(0, 8)
    items = [rng.randint(0, 5)
             for _ in range(n)]
    out = dedupe(items)
    assert set(out) == set(items), items
    assert len(out) == len(set(out)), items
print("300 inputs, no failure")

• A round trip gives back the input: decode(encode(x)) == x.
• Nothing is lost or invented: the sorted input equals the sorted output.
• The output has the promised shape, such as being sorted.
• A slow, obviously correct version agrees with the fast one.

Generate small values, so duplicates, negatives and empty lists come up often, and put the input in the assert message: a failure is only useful if you can reproduce it.

merge_sorted(a, b) is written for you. Write test_merge_properties(): using random.Random(0), generate at least 200 pairs of sorted lists, each 0 to 6 long with values from -5 to 5, and assert that each result is sorted and holds exactly the items of a + b, with the inputs in the messages.

The explanation opens here once every check passes.