The important caveat about quicksort is that its worst-case performance is O("n"2); while this is rare, in naive implementations (choosing the first or last element as pivot) this occurs for sorted data, which is a common case. The most complex issue in quicksort is thus choosing a good pivot element, as consistently poor choices of pivots can result in drastically slower O("n"2) performance, but good choice of pivots yields O("n" log "n") performance, which is asymptotically optimal. For example, if at each step the median is chosen as the pivot then the algorithm works in O("n" log "n"). Finding the median, such as by the median of medians selection algorithm is however an O("n") operation on unsorted lists and therefore exacts significant overhead with sorting. In practice choosing a random pivot almost certainly yields O("n" log "n") performance.