Is there an algorithm with linear time complexity to calculate the rank sum statistic? Definition 1: For a real array $x = (x_1, \dots, x_n)$, denote  the rank of $x_i$ in $(x_1,\dots, x_n)$ by the following:
$$
r_{i}=\sum_{j=1}^{n} I_{\left(x_{j} \leq x_{i}\right)}, \quad 1 \leq i \leq n
$$
Given 2 independent samples $X = (X_1,\dots, X_m)$ and $Y = (Y_1,\dots ,Y_n)$, we mix the 2 samples and denote the mixed sample by $(X_1,\dots, X_m,Y_1,\dots ,Y_n)$. Denote the rank of the mixed sample by
$$
S=\left(Q_{1}, \cdots, Q_{m}, R_{1}, \cdots, R_{n}\right)
$$
The rank sum of $Y$ in the mixed sample is denoted by $\sum_{j=1}^{n}R_j$
Question: Is there an algorithm with linear time complexity to calculate the rank sum $\sum_{j=1}^{n}R_j$?
 A: I don't think that this is possible. The rank is equal to the position in the sorted array. It is known that the lower bound for comparison based sorting is $\Omega(n\log n)$ which can be shown by inspecting the decision tree. This means that if you can calculate the rank of each element in linear time, you have a better sorting algorithm than the theoretical lower bound.
However, if your individual samples are already sorted, then you can use the "merge step" of the merge sort which has a complexity of $\mathcal{O}(n+m)$ to get the combined sorted array. This can be seen here (python implementation):
    # Copy data to temp arrays L[] and R[] 
    while i < len(L) and j < len(R): 
        if L[i] < R[j]: 
            arr[k] = L[i] 
            i+= 1
        else: 
            arr[k] = R[j] 
            j+= 1
        k+= 1
      
    # Checking if any element was left 
    while i < len(L): 
        arr[k] = L[i] 
        i+= 1
        k+= 1
      
    while j < len(R): 
        arr[k] = R[j] 
        j+= 1
        k+= 1

