Merge Sort and Complexity | Dataford Interview Questions

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.

Formal Specification

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.

Constraints

0 <= len(records) <= 10^5
Every record contains field
Field values are mutually comparable using <=
Record dictionaries may contain additional fields
Do not use sorted or list.sort

Function Signature

def sort_records(records, field):

Your question is Merge Sort and Complexity. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem