Implement a Sorting Algorithm | Dataford Interview Questions

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

Dell PowerStore monitoring tools receive event records that must be displayed consistently. Implement a sorting algorithm of your choice to return the records ordered by timestamp ascending, then by severity descending. Records with identical keys must retain their original relative order.

Do not use Python's built-in sort() or sorted() functions, and do not modify the input list.

Formal Specification

Implement sort_powerstore_events(events). The input is a list of dictionaries, where each dictionary contains:

id: a string identifying the event
timestamp: an integer timestamp
severity: an integer from 1 through 5, where 5 is most severe

Return a new list containing the same dictionaries in the required order. The algorithm must be stable.

Constraints

0 <= len(events) <= 100,000
0 <= timestamp <= 10^12
1 <= severity <= 5
Every record contains valid id, timestamp, and severity fields

Function Signature

def sort_powerstore_events(events):