Problem. Given model scores s (n) and binary labels y (n), compute the area under the ROC curve (AUC). Equivalently:
AUC = P(score of a random positive > score of a random negative), with ties counting 1/2
s = [0.1, 0.4, 0.35, 0.8], y = [0, 0, 1, 1]
pairs (pos, neg): (0.35, 0.1) ✓ (0.35, 0.4) ✗ (0.8, 0.1) ✓ (0.8, 0.4) ✓ → AUC = 3/4
The pairwise definition is the clearest one, and it's also the brute force: P · N comparisons. Sorting turns it into counting: in sorted order, each positive beats exactly the negatives ranked below it. Summing the ranks of the positives gives the count of (positive, negative) wins in one pass.
ML context. AUC is the standard metric for ranking quality and imbalanced binary classification (fraud, click-through, medical screening) because it doesn't depend on a threshold. Implementing it from scratch, including ties, is a classic ML-round question, and evaluating on hundreds of millions of predictions needs the O(n log n) or histogram version.