Sorting Algorithm Problem | Dataford Interview Questions

Your question is Sorting Algorithm Problem. 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.

Problem

Bentley iTwin services receive model update records that must be processed in a deterministic order. Implement a stable merge sort to order updates by priority, timestamp, and element identifier.

Each update is represented as a dictionary with keys element_id, priority, and timestamp. Return a new list without modifying the input. Sort using these rules, in order:

Higher priority values come first.
For equal priorities, earlier timestamp values come first.
For equal priority and timestamp, lexicographically smaller element_id values come first.
If all sort fields are equal, preserve the original input order.

Do not call Python's built-in sorted() or .sort(). Your implementation should use merge sort and may define helper functions.

Formal Specification

Implement sort_model_updates(updates), where updates is a list of dictionaries. Return a new list containing the same dictionaries in the required order. Timestamps are integers, and priorities are integers.

Constraints

0 <= len(updates) <= 100,000
-10^9 <= priority, timestamp <= 10^9
Each update contains valid element_id, priority, and timestamp fields
element_id is a non-empty string of at most 100 characters

Function Signature

def sort_model_updates(updates):