Worst Case: O(n)

It is not possible for a comparison sorting algorithm to opperate at this speed in the worst case.