You have an array of businesses. Each business has an ID
\[n \in \left[1..10000\right]\]
and a rating
\[m \in \left[1..5\right]\]
You want to output the business ids sorted by rating (highest to lowest), with businesses with the same rating respecting the order above.
which runs in in O(n) time and outputs