In-Place Merge of Two Halves | Dataford Interview Questions

An array has elements as [0th, 2nd, 4th, 6th, ..., 1st, 3rd, 5th, 7th, ...] where each Nth is the relative rank of the element; merge the two halves in-place (no extra memory) into ascending order.

Asked in the technical interview stage. Implement the operation for an even-length list whose two contiguous halves are individually sorted.

Contract

Implement def merge_ranked_halves(nums):. Modify nums in place and return it. Use O(1) auxiliary space.

Constraints

2 <= len(nums) <= 1000
len(nums) is even
The first half is sorted in nondecreasing order
The second half is sorted in nondecreasing order
-10^9 <= nums[i] <= 10^9

Function Signature

def merge_ranked_halves(nums):

Your question is In-Place Merge of Two Halves. 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