Question:
Describe the algorithm of Quicksort. Be sure to capture the main ideas behind 
the algorithm. Give the worst-case and average-case running time in big Oh notation.
When does the worst-case happen?

Answer:
Quicksort is a divide and conquer algorithm that takes
an input array of n numbers and sort these n numbers into increasing order. 

An element of the input array (e.g., the last element) is picked 
as a pivot element. All other elements are compared to 
the pivot element and are positioned to the left side if smaller
than the pivot and to the right side if otherwise.
As a result, the input array is partitioned into two subarrays, with
the left subarray containing only elements smaller than the pivot
and the right subarray containing only elements larger than the pivot.

And such partitioning process is applied recursively on the subarrays;
The recursion terminates when subarrays contain single element,
and the whole array is thus sorted.

The worst-case time complexity is O(n^2).
The average-case time complexity is O(n log n).

If the algorithm always picks the last element as pivot, the
worst-case is an input array of n numbers that are already
sorted in increasing order.