Even it it was O(1) not amortized, it's not possible to beat the sorting in actual execution time for reasonable inputs (less than 10B elements probably)