Your question is Merge Sort and Complexity. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
DMI services may need predictable ordering when sorting records displayed in a digital service workflow. Implement a stable merge sort that orders records by a specified field without using Python's built-in sorting functions.
Implement sort_records(records, field), where records is a list of dictionaries and field is a string containing a key present in every record. Return a new list sorted in ascending order by record[field].
The algorithm must be stable: if two records have equal field values, they must remain in their original relative order. Do not mutate records, call sorted, or call .sort().
Use either recursive divide-and-conquer or an iterative bottom-up design. Explain why merge sort has O(n log n) time complexity and O(n) auxiliary space complexity.
def sort_records(records, field):