SORTING BY RANKING

{rank of an item=number of items smaller}

rank each item by counting;
then place each item according to its rank.
If duplicate, then place it at the nearest slot to the right.

$W(n)=O(n(n-1))=A(n)=B(n)$

$S(n)=O(n)$

To handle duplicates, redefine
rank(i) = number of items smaller than i or, if equal, occurring before i.
Oblivious Algorithm