#618 · Sorting and searching · Advanced · Find and fix · 120 XP · about 20 min
merge_sort(items, key) should return a new list of items sorted by key(item), from smallest to largest, using merge sort. The sort must be stable: items with equal keys stay in the order they had in the input. The input list is not changed.
The code in the editor has two bugs. Some items go missing from the result (merge_sort([1, 2], key=lambda x: x) gives [1]), and items with the same key sometimes swap places.
merge_sort([5, 4, 3, 2, 1], key=lambda x: x) # returns [1, 2, 3, 4, 5] merge_sort([('b', 1), ('a', 1)], key=lambda p: p[1]) # returns [('b', 1), ('a', 1)] merge_sort(['pear', 'fig', 'banana', 'kiwi'], key=len) # returns ['fig', 'pear', 'kiwi', 'banana']
In the last example 'pear' and 'kiwi' both have 4 letters, so they keep their input order.
items has 0 to 5,000 items.First solves only, ranked by stars and then time.