Editing 3026: Linear Sort

{{comic
| number    = 3026
| date      = December 18, 2024
| title     = Linear Sort
| image     = linear_sort_2x.png
| imagesize = 385x181px
| noexpand  = true
| titletext = The best case is O(n), and the worst case is that someone checks why.
}}

==Explanation==
A common task to have computers do is to sort a list, such as from A to Z or from the smallest to the largest number. People have created dozens of algorithms for this task, from simple to complex, each with its own merits on ease of implementation, memory usage, and efficiency; to understand the last one, for this and all other uses of algorithms, computer scientists adopted {{w|Big O Notation}}. There are two aspects of Big O notation to know:

1. It is ''asymptotic''; meaning that it simply expresses the base relation between the size of the list and the time needed to sort. O(2''n'') is written simply as O(''n''), because Big O is more concerned about indicating the sort time scaling linearly rather than accurately giving you a formula to calculate how long it'll take. Likewise, O(2<sup>''n''</sup> + ''n''<sup>2</sup>) might be written as O(2<sup>''n''</sup>) because the value of ''n''<sup>2</sup> would eventually become small enough (relative to 2<sup>''n''</sup>) to be rounded off.

2.Big O notation is only an average estimation. The actual figure depends on the hardware, software, and the initial state of the list - consider if you needed to sort a pile of books by title you might luck to find most books are already in the correct position and only need to move one or two, or they might be hopelessly jumbled up and necessitate moving most, even all of them. Big O notation is mainly used to examine various methods to accomplish the same task, running on the same hardware, rather than being real-world benchmarks.

A few common Big O notations are listed below, from smallest to largest:
<ul><li><b><i>O</i>(1)</b> - Constant time, which means the sorting will always take X seconds no matter how big the data is</li>
<li><b><i>O</i>(log(''n''))</b> - Logarithmic time, which means the executing time grows only a little when the input grows a lot</li>
<li><b><i>O</i>(''n'')</b> - Linear time, which means the execution time grows in direct proportion to the size of the data</li>
<li><b><i>O</i>(''n'' log(''n''))</b> - The execution time grows proportionally to ''n'' times the {{w|logarithm}} of ''n''.</li>
<li><b><i>O</i>(''n''<sup>2</sup>)</b> - Quadratic time, meaning the execution time grows proportionally to the ''square'' of the size of the data.</li></ul>

As one can image in most contexts one would wish for sorting to be done as fast as possible, so O(1) is better than O(n), which is in turn better than O(n*log(n)) etc (at least assuming your lists are relatively large).  The code in the comic describes a 'linear' sort that first sorts the list using {{w|merge sort}}, which is known to take time O(''n'' log(''n'')), and then `sleep()`s (pauses with no activity) for an amount of time equal to subtracting the time taken for the sort from the number of elements multiplied by 1 million (1e6) seconds. Here the joke is that, rather than creating an algorithm that actually takes O(n) time it simply disguises an algorithm that takes O(n*log(n)) and makes it appear to be O(n) - and if 2 and 4 lines are removed, it will indeed work like O(n*log(n)). The runtime is much longer than mergesort's, but it increases linearly with the length of the list, so it appears to be O(n). This is obviously not ideal as waiting around doing nothing is the opposite of optimization.{{cn}}

This joke is carried on by the title text, which refers to the {{w|Best, worst and average case|best and worst case}} of a sort, which are additional measures of its runtime to describe the shortest and longest potential times. A more optimal sort may decide how much of a list needs to be passed over again after its first pass of shuffling elements around; scanning a pre-sorted list (and deducing that it has no more checking to do) could mean that no more effort is needed, resulting in a best case of O(''n''). Depending upon the algorithm, presenting a list that is in an ordering that happens to challenge it the most (such as exactly reversed) may mean even an 'average O(''n'' log ''n'')' process would have to exceed this, resulting in a worst-case number of operations that may be O(''n<sup>2</sup>''). It can be very useful to know that a given sorting method ''may'' take the average order of time, but have the possibility of a much shorter ''or'' longer runtime... especially when the method is expected to be [[1185: Ineffective Sorts|far, far worse than others]], where only particular and more idealistic input lets it approach the more satisfyingly fast average/best responses.

By forcing all practical searches to take O(''n'') time, regardless of how otherwise identical data is presorted, the best case (and worst case, for that matter) will also be O(''n''). The last part of the text then plays on another meaning of best case and worst case, as best- and {{w|worst-case scenario}}s for a situation, by saying that the worst outcome for the code's author is when someone decides to investigate the code (perhaps owing to its absurd runtime, or else just justifiably skeptical of the declared optimality), whereupon that investigator will discover the deception and ruin the author's reputation.

One possible advantage, to doing something ''like'' this, could be to prevent some form of {{w|timing attack}} from being effective, but it is highly doubtful that this would be usefully applied either to the implementation of a sort ''or'' with such an excessive inbuilt delay factor.

It is worth noting that almost every time someone uses a big O on this page, they actually mean a big theta. Those aren’t the same thing. If you say something happens in Θ(f(N)) time, then f(N) is how long it takes (within a constant factor) in the limit for large N. In other words, it takes asymptotic time f(N). But if it takes O(f(N)) time, then the limit is at most f(n), but might actually be much lower. So mergesort takes O(N log N) time. And it also takes O(2^N) time. And it takes Θ(N log N) time. But it does NOT take Θ(2^N) time.

==Transcript==
{{incomplete transcript|Do NOT delete this tag too soon.}}
:[The panel shows five lines of code:]
:function LinearSort(list):
::StartTime=Time()
::MergeSort(list)
::Sleep(1e6*length(list)-(Time()-StartTime))
::return

:[Caption below the panel:]
:How to sort a list in linear time

{{comic discussion}}

[[Category:Programming]]