I need to describing a Turing machine that computes $\lceil\log_{2}(n)\rceil$ I know that:

n = 1, 2, 3, 4, 5, 6, 7, 8, ... 
f(n) = 0, 1, 2, 2, 3, 3, 3, 3, ...

So I'm thinking of putting $n$ on the tape. Then keeping a count of how many times I multiply 2*2 until it is greater than than $n$. For example for n=5, 2*2*2=8, number of two's is 3 so then $f(n)$ is 3. I don't know how to translate this to the ticker tape of the Turing machine.

But would something like this work? Put $n$ 1's on the tape followed by a 0. Compute 1^(2^1), then check if 1's on the left of the 0 on the tape is less than or equal to the 1's on the right of the 0. If its not then repeat it for 1^(2^(1)). It keeps doing this until the left side has less than or equal number of 1's.

In general terms, there are the $O(n^2)$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $O(n^2)$ but quite often $O(n\log n)$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $O(n\log n)$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms; and the $O(n)$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists.

If the elements in your list are such that all you know about them is the total order relationship between them, then optimal sorting algorithms will have complexity $\Omega(n\log n)$. This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements.

Even more generally, optimality of a sorting algorithm depends intimately upon the assumptions you can make about the kind of lists you're going to be sorting (as well as the machine model on which the algorithm will run, which can make even otherwise poor sorting algorithms the best choice; consider bubble sort on machines with a tape for storage). The stronger your assumptions, the more corners your algorithm can cut. Under very weak assumptions about how efficiently you can determine "sortedness" of a list, the optimal worst-case complexity can even be $\Omega(n!)$.

This answer deals only with complexities. Actual running times of implementations of algorithms will depend on a large number of factors which are hard to account for in a single answer.
