Comment by Paedor

For 1) The asymptotic best for sorting is O(n log n), if you're only allowed to compare the size of elements. If you allow operations like array indexing with elements, which is possible for integers, it gets as good as O(n) with radix sort.