O(n log n) Sorting Algorithm | Dataford Interview Questions

Your question is O(n log n) 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

PlayStation Network may need to order game download sizes before displaying them in a storage-management view. Implement a sorting algorithm that returns the sizes in ascending order without calling Python's built-in sorting functions.

Use merge sort or another comparison-based algorithm with guaranteed O(n log n) time complexity. The input list may be modified, but returning a new sorted list is also acceptable.

Formal Specification

Implement sort_download_sizes(sizes).

Input: sizes, a list of integers representing download sizes in gigabytes.
Output: A list containing the same integers as sizes, sorted in nondecreasing order.
Duplicate values must be preserved.
The algorithm must not use sorted() or list.sort().

Constraints

0 <= sizes.length <= 10^5
-10^9 <= sizes[i] <= 10^9
Do not use sorted() or list.sort()
The worst-case running time must be O(n log n)

Function Signature

def sort_download_sizes(sizes):