StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There's no quick one sentence explanation. Quick sort is actually O(<em>n</em><sup>2</sup>) in the worst case but it is O(<em>n</em> log <em>n</em>) on average, so if you try to analyze it you will not be able to prove that it is always O(<em>n</em> log <em>n</em>). It is only O(<em>n</em> log <em>n</em>) <strong>on average</strong>, averaged across all possible data sets. For any particular list it might be worse.</p> <p>If the pivots end up being really, really bad then quick sort will perform very badly. This can happen on already sorted data, for instance, if you always choose a fixed element at the beginning or end of the array as the pivot element.</p> <p>Other sorting algorithms like merge sort and heap sort, on the other hand, are always O(<em>n</em> log <em>n</em>). They do not have pathological cases where their performance degrades to O(<em>n</em><sup>2</sup>). This makes them preferable if what you desire is consistent, predictable performance at all times. The advantage of quick sort is that is overall a faster algorithm on average, just not always so.</p> <p><strong>Edit</strong>: Indeed, as <strong>@pst</strong> says, merge sort requires O(<em>n</em>) space when sorting arrays (scratch space for the merges), which is less than ideal. That's a point against it. But then another point against quick sort is that it is an unstable sort. Elements that are equal to each other may be shuffled around after the sort.</p> <p><a href="http://bugs.python.org/file4451/timsort.txt" rel="nofollow noreferrer">Timsort</a> is an awesome new search algorithm—well, less new, more a great combination of existing algorithms plus a lot of fine tuning and clever optimizations (the galloping thing is money). Read that text file for a glimpse of Great Programming.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload