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==
{{incomplete|Created in Θ(N) TIME by an iterative Insertion Sorter working on a multidimensional array - Please change this comment when editing this page. Do NOT delete this tag too soon.}}
A common task in programming is to sort a list, a list being a collection of related elements of data that are stored in a linear fashion. There are dozens of algorithms that have been created for this through the years, from simple to complex, and each has its own merits with regards to how easy it is to understand / implement, how much space it uses, and how efficiently it operates on the data.

In computer science, the runtime of an algorithm can be described using {{w|Big O Notation}}, which categories the asymptotic, usually average, runtime (''O'') of a function of the number of elements (''n'') operated on (''f(n)'') as it grows larger and larger towards infinity; this creates the form O(''f''(''n'')) as the final description. Being asymptotic means that Big O Notation only considers parts of the function that scale with time and disregards fixed changes such as multipliers and additions to the scaling time. For instance, in an O(''n'') algorithm, ''f''(''n'') is simply ''n'', meaning it takes a constant amount of time per element operated on. A simple example would be examining pictures: if it takes one second to look at a picture, it would take ten seconds to look at ten pictures; if it took three seconds to look at a picture, it would take thirty seconds to look at ten pictures - both are described as O(''n'').

Generally, programmers seek to minimize the Big O Notation of their algorithms because it means they take less time. It can be proven that the best general-purpose sorting methods are O(''n'' log ''n''); since this is larger than ''n'' on its own, it means that algorithms will always begin to take longer per element as the number of elements increases.

Here are some examples of common runtimes expressed in Big O notation, from smallest to largest:
<ul><li><b><i>O</i>(1)</b> - Constant time, which means the execution time is independent of the size of the data</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'' * the {{w|logarithm}} of ''n'', with the added ''log(n)'' creating an increasingly larger multiplier on the runtime</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>

The code in the comic describes a 'linear' sort that first sorts the list using {{w|merge sort}}, which takes time O(''n'' log(''n'')), and then `sleep()`s (pauses with no activity) for an inverse amount of time by subtracting the time taken for the sort from 1e6 (1 million) seconds so that the total time always equals that amount. This effectively converts the algorithm through brute force to fit the definition of linear time: it takes one million seconds - which is more than 11 days - per element, regardless of the number of elements. The joke is that although this algorithm runs in O(''n''), it is actually significantly slower than the usually worse O(''n'' log(''n'')) the sort would run on its own.

It should be noted that for sufficiently large lists, the merge sort will take longer than the million seconds per element, which might crash the program as it attempts to sleep for a negative amount of time.  However, this issue will only arise for impossibly huge lists: if, for instance, a merge sort took ''n log(n)'' microseconds to complete(slow by today's standards), then the comic's 'linear' sort would take shorter than merge sort only for lists longer than 2<sup>1,000,000,000,000</sup> ≈ 10<sup>300,000,000,000</sup> elements - a number far larger than the number of atoms in the universe. The impossibility of this outcome might be why such a ridiculously high number of seconds was chosen.

The title text refers to the {{w|Best, worst and average case|best and worst case}} of a sort, which are additional measures of its runtime describing the shortest and longest potential times. This arises when a given sort decides how much of a list needs to be passed over again when the initial scan has identified a need to shuffle elements around; scanning a pre-sorted list (and deducing that it has no work to do) would only pass the one time and result in a best case of O(''n''). Depending upon the algorithm, presenting a list that is reverse-sorted (or perhaps in some other specific ordering that happens to challenge it the most) may require even an 'average O(''n'' log ''n'')' process to take a worst-case number of operations of something like 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]] outside of ideal, rare conditions that cause it to be faster.

By forcing all practical searches to take O(''n'') time regardless of how identical data is provided for sorting, the best case (and worst case, for that matter) will, in fact, still be O(''n''). The last part of the text then plays on the another meaning of best case and worst case as best- and {{w|Worst-case_scenario|worst-case scenarios}} for a situation, saying that the worst situation that could occur for the code's author is if someone decides to investigate the code (perhaps owing to its absurd runtime), where they will discover the deception and probably lead to some sort of punishment for it.

==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]]