Double argsort for ranks of NumPy arrays

The Mathematical Rationale Behind Double Argsort for Array Ranking in NumPy

Applying np.argsort(np.argsort(x)) twice yields element ranks in an array without specialized functions. This works for arrays with unique values and accounts for original positions with duplicates. Unlike scipy.stats.rankdata, which starts at 1, double argsort uses zero-based indexing and is equivalent to the method='ordinal' approach.

Consider the array a = [13, 0, 47, 52, 27]. The sorted version is s = [0, 13, 27, 47, 52]. The first argsort gives indices [1, 0, 4, 2, 3], the second yields ranks [1, 0, 3, 4, 2], matching rankdata(a, method='ordinal') - 1.

import numpy as np
from scipy.stats import rankdata

a = np.array([13, 0, 47, 52, 27])
print("a:", a)
s = np.sort(a)
print("s = sort(a):", s)
m = np.argsort(a)
print("m = argsort(a):", m)
p = np.argsort(m)
print("p = argsort(argsort(a)):", p)
r = rankdata(a, method="ordinal") - 1
print("r = rank(a):", r)

Output:

a: [13 0 47 52 27]
s = sort(a): [0 13 27 47 52]
m = argsort(a): [1 0 4 2 3]
p = argsort(argsort(a)): [1 0 3 4 2]
r = rank(a): [1 0 3 4 2]

Formalizing the Problem

Define:

• a = (a_1, ..., a_N) — the original array.
• s = (s_1, ..., s_N) — sorted in ascending order.
• m = argsort(a) — indices where a_{m_i} = s_i.
• p = argsort(m) — the double argsort.
• r = (r_1, ..., r_N) — ranks where s_{r_i} = a_i.

Goal: Prove p_i = r_i for all i.

With duplicates, double argsort assigns a lower rank to the element with the smaller original index, ensuring unique ranks.

Step-by-Step Proof

• Array m is a permutation of {1, ..., N}, all m_i are unique: m_i ≠ m_k for i ≠ k.

• p = argsort(m) orders m in ascending order: m_{p_1} < m_{p_2} < ... < m_{p_N}, since equalities are impossible. Thus, m_{p_i} = i for all i.

• From the argsort property: a_{m_i} = s_i. Substitute i = p_k: a_{m_{p_k}} = s_{p_k}.

• From step 2, m_{p_k} = k, so a_k = s_{p_k}.

• This means p_k is the position of a_k in the sorted array s, i.e., the rank: p_i = r_i.

The proof confirms correctness for arrays of any dimension with NumPy's stable sorting.

Practical Application Aspects

• Stability: NumPy argsort is stable, so equal elements retain their index order.
• Performance: Double argsort is faster than rankdata for large arrays without method customization.
• Limitations: Works only for real or integer arrays; for string arrays, use lexicographic order.

Usage scenarios list:

• Computing percentiles in data science pipelines.
• Ranking features in ML models before normalization.
• Building confusion matrices based on predicted ranks.
• Analyzing time series to identify local extrema.

Key Takeaways

• Double argsort(argsort(x)) is equivalent to zero-based ranks with the ordinal method.
• The proof relies on permutation properties and argsort composition.
• With duplicates, ranks are unique and depend on the original order.
• More efficient than rankdata for simple cases without extra parameters.
• Suitable for mid- to senior-level developers in data processing tasks.

— Editorial Team