Backpropagation Through Sort and Median

Consider the function f: R^n -> R^n that sorts an input vector in ascending order and divides every sorted element by the median of the input:
def f(x):
return np.sort(x) / np.median(x)
For example, f([3, 2, 1]) = [1/2, 1, 3/2].
Gradient task
You are given the input vector x and an upstream gradient v = dL/dy, where y = f(x). Compute and return dL/dx.
A runtime that is roughly linear in n, allowing logarithmic factors such as sorting, is acceptable.

Function
backpropSortMedian(x: double[], v: double[]) → double[]

Examples
Example 1
x = [3.0,2.0,1.0]
v = [1.0,1.0,1.0]
return = [0.5,-1.0,0.5]
The direct contribution through sorting is 1 / 2 for each original element. The median element 2 also receives the denominator contribution -(1 + 2 + 3) / 2^2 = -3/2, so its total gradient is -1.

Constraints
n is odd.
The median is unique.

Split the gradient into two parts. Let m be the median and s the sorted x. Output y_i = s_i / m. First part: the sorted element at rank i came from original index p_i, so x[p_i] gets v_i / m. That's a scatter through the argsort permutation. Second part: the median depends on x, and only the element at the median rank has derivative 1 with respect to m. dL/dm = sum over i of v_i * (-s_i / m^2). Add that scalar to the gradient of the original index holding the median. Check it against example 1: the median element 2 gets 1/2 plus -(6)/4 = -1. The pitfall is forgetting the denominator term, or applying it to every element instead of just the median index. Argsort once, then do everything in O(n log n). If the chain rule slips away live, StealthCoder is your hedge.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.