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==
{{w|Sorting algorithm}}s are a fundamental part of computer science, with various methods differing in efficiency, ease of implementation, and resource usage. Efficiency is often described using {{w|Big O notation}}, which expresses how the runtime of an algorithm scales with the size of the input. For example, "O(''n'')" ("linear time") means the runtime grows proportionally to the size of the input, while "O(''n'' log ''n'')" means it grows slightly faster than linear. Faster algorithms, like O(''n''), are generally preferred for large datasets.

The comic presents a humorous "linear time" sorting algorithm that first uses {{w|merge sort}}, a well-known O(''n'' log ''n'') algorithm, to sort the list. It then "sleeps" for an additional amount of time to artificially make the runtime scale linearly with the size of the input. Specifically, it pauses for <code>(1 million) * length(list) - (time spent sorting)</code> seconds, which is perhaps large enough (in the case of all practical implementations) to stretch to a knowable point beyond the actual time spent sorting, ensuring the overall runtime appears to grow linearly. This is a joke because the actual sorting is still O(''n'' log ''n''); the additional sleep time is simply wasted time to give the illusion of linear time. It's also a joke because it makes the sort so slow that it's useless, with a "sort" of one item taking upwards of 11 ''days'', two items taking 23 days, three taking 34 days, and so on.

The humor lies in the absurdity of intentionally slowing down a sorting algorithm to match a desired runtime profile. This defeats the purpose of optimization, as the goal of sorting algorithms is typically to minimize time spent, not to pad it with unnecessary delays. (Delays may be necessary for other functional reasons, but are an antithesis of the kind of optimality sought here.) If the artificial sleep were removed, the algorithm would revert to its true O(''n'' log ''n'') efficiency, making the "linear sort" label both deceptive and wastefully unnecessary.

The title text extends the joke by referencing "best" and "worst" cases, concepts in {{w|algorithm analysis}} that describe how the runtime varies with different inputs. For the "linear sort," the best and worst cases are identical because the sleep function forces the runtime to always be O(''n''), regardless of the input. The "worst case for the author," however, is when someone examines the code, exposes the fraud, and damages their reputation—a humorous twist on the idea of worst-case scenarios.


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