I wouldn't agree that quicksort is better than other sorting algorithms in practice.
For most purposes, Timsort - the hybrid between mergesort/insertion sort which exploits the fact that the data you sort often starts out nearly sorted or reverse sorted.
The simplest quicksort (no random pivot) treats this potentially common case as O(N^2) (reducing to O(N lg N) with random pivots), while TimSort can handle these cases in O(N).
According to these benchmarks in C# comparing the built-in quicksort to TimSort, Timsort is significantly faster in the mostly sorted cases, and slightly faster in the random data case and TimSort gets better if the comparison function is particularly slow. I haven't repeated these benchmarks and would not be surprised if quicksort slightly beat TimSort for some combination of random data or if there is something quirky in C#'s builtin sort (based on quicksort) that is slowing it down. However, TimSort has distinct advantages when data may be partially sorted, and is roughly equal to quicksort in terms of speed when the data is not partially sorted.
TimSort also has an added bonus of being a stable sort, unlike quicksort. The only disadvantage of TimSort uses O(N) versus O(lg N) memory in the usual (fast) implementation.
You don't implement amortized analysis. It's a technique to get more accurate O bounds.
The essential observation you have to make is, that expensive operations cannot happen at any time.
In the case of an array-backed data structure, the array needs resizing every now and then – when it's full. This is the most expensive operation and takes O(n) time. All other inserts into the array are O(1).
To determine the runtime for inserting n items, you can multiply n with the most expensive operation O(n), which results in an overall runtime behavior of O(n^2).
However, this is inaccurate because resizing cannot happen very often.
When talking about money, you amortize cost, when you pay off your debt with multiple small payments over time.
We can use this model to think about algorithms as well. We simply substitute "time" with "money" to avoid mental mapping.
Once the array is fulled to it's length n, we can double it's size. We need to make the following operations:
- Allocate
2n chunks of memory
- copy
n items
If we assume that both allocating memory and copying happen in linear time, this is going to be a very expensive operation. However, we can now use the idea of debt and amortizing it for our analysis. Only, we are going to amortize our debt before we actually make it.
Let's assume, that our balance (of money/time) is back to 0 (i.e. we don't have a debt nor do we have any leftovers) once we have resized the array.
This has the following implication:
- Inserting the next
n items will cover the cost of resizing and copying (we have n used slots, and n unused slots`)
We can now think about how much every insert operation needs to pay for:
- The insert
- The cost of allocating one chunk of memory
- the cost of moving it to the newly allocated memory
We have now covered the costs to allocate memory, copy and insert the next n elements. However, we have yet neglected allocating space for the old n elements as well as copying them.
We simply distribute the costs of our old n elements to our new (yet to be inserted) n elements:
- The cost of allocating one chunk of memory
- the cost of moving it to the newly allocated memory
In total, every, every insert operation will cost 5 units. This pays for its own insertion, and the moving and allocating of space for itself and one of the old elements.
Every insert-operation still takes constant amount of time, but the resizing happens for free: We amortized it by spending "more" time on each insertion.
As a result, inserting n elements takes O(n) time.
Other techniques for amortized analysis are explained here.
Best Answer
Expected time is just the average, expected, running time of the algorithm using the intended input.
Say you've got some few million user records and want to sort them, you might want to use an algorithm which is the most suitable for your input, and as such gives the best expected running time, as opposed to an algorithm which has better worst-case running time but worse expected running time.
Sometimes for example the constant factors for the time-complexity of an algorithm are so high that it makes sense to use algorithms with worse time-complexity but smaller constant factors, as it gives you better expected running time with small input, even though it would get horribly outperformed with bigger input.
Perhaps a better example would be the classic quicksort algorithm, which has worst-case running time of O(n²) but expected average running time of O(n log n), regardless of input. This is because the algorithm uses(or rather, may use, depending on the implementation) randomization. So it's a so-called randomized algorithm. It runs a bit differently with every invocation even with the same input. As such, thre's no universal worst-case input for the implementation, because the worst-case input depends on the way the algorithm chooses the pivot for dividing the given input. And as such, one can't just supply some pre-defined input causing the worst-case running time. This is often the case with randomized algorithms, which aim for better expected, average running time regardless of the input.
It's all about using the right algorithm for the input at hand.