如何有效地确定数组中每个元素的等级（在平局情况下平均）？例如：

float[] rank(T)(T[] input) {
    // Implementation
}

auto foo = rank([3,6,4,2,2]);  // foo == [3, 5, 4, 1.5, 1.5]

我能想到的唯一方法是分配3个数组：

1. 输入数组的重复项，因为必须对其进行排序，并且我们不拥有该数组。
2. 一个数组，用于跟踪输入数组的排序顺序。
3. 要返回的等级数组。

有谁知道如何在O（N log N）时间和O（1）辅助空间中执行此操作（这意味着我们必须分配的唯一数组是要返回的数组），或者至少摆脱了其中一个上面的三个数组？