Median of a large unsorted array in linear time

You are given a very large, unsorted list of integers nums. Return its median.

• If len(nums) is odd, the median is the middle value once the list is sorted.
• If len(nums) is even, the median is the average of the two middle values once the list is sorted.

Implement find_median(nums: list[int]) -> float.

Sorting the whole list is too slow for the data sizes we care about. Your solution must run in expected (average) O(n) time.

Constraints

• 1 <= len(nums) <= 10^7
• -10^9 <= nums[i] <= 10^9
• Values may repeat, and the list may contain long runs of the same value.
• Do not change the caller's list unless you say so and explain the trade-off.

Example 1

nums = [9, 2, 7, 4, 5]
Output: 5.0

Sorted, the list is [2, 4, 5, 7, 9]. The middle value is 5.

Example 2

nums = [8, 3, 3, 12, 1, 6]
Output: 4.5

Sorted, the list is [1, 3, 3, 6, 8, 12]. The two middle values are 3 and 6, and their average is 4.5.

Reconstructed from the reported question; details may differ from what interviewers ask.