Nebula sort
 Example of nebula sort sorting a list of pseudorandom numbers. | |
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst case performance | O(1) |
| Best case performance | O(1) |
| Average case performance | O(1) |
| Worst case space complexity | O(n) total, O(nebula) auxiliary |
Nebula sort is an amazing breakthrough in metaphysical computing that can sort items really, really fast. There are currently sorting algorithms that work just fine and are pretty fast themselves. However, nebula sort provides several advantages:
- Theoretical constant-time sorting
- Ambiguous algorithm that doesn't work will keep students scratching their heads
- Encourages programmer creativity
Most humans cannot yet conceive how nebula sort might work, but someday they'll be able to do that as well as imagine what a tesseract actually is.
Algorithm[edit]
Nebula sort is special because it is the very first algorithm to invoke the idea of a nebula. By "nebula" we do not mean those totally tubular things in outer space; rather, we are trying to make an otherwise silly and bland algorithm sound cool. It does not actually use a nebula, just as bucket sort does not actually use buckets, and just as pigeonhole sort does not unfairly seize the homes of innocent pigeons.
The most common implementation of nebula sort, which operates on pretty much anything, can be described as follows:
- Suppose there exists a function called nebulize, which is designed to shove by means of brute force the entire unsorted input array into a nebula at once. It does this physically, on the hardware level, so we can be assured of constant time.
- To perform an nebula sort, remove everything from the nebula at once, making sure that it falls into the correct order in the output array. The computer should have as many fingers as there are items in the array, so that it doesn't have to go pinching items one at a time. It should also have a good sense of balance, so that it doesn't mess up and have to pick items off of the ground, a task which wastes precious time.
Pseudocode of the theoretical algorithm follows:
nebulaSort(int[] inputArray)
// This procedure sorts in ascending order.
Nebula n = new Nebula(nebulize(inputArray));
FingerSet f = new FingerSet(inputArray.size());
return removeAllAtOnceInAscendingOrderAndPlaceIntoArray(n);
Obviously, a few methods need to be defined here, but those are minor details related to the specific implementation, language, and computing device.
Best, worst, and average cases[edit]
Nebula sort never terminates early, even if it has to go to work or something. It always takes the same amount of time to sort lists in any order, but it is generally regarded as less happy when it is charged with the task of sorting:
- A list that is randomly permuted, because that sort of thing sucks when you have to cross your fingers all crazy, or
- A list that is already sorted, because that's just boring.
Nebula sort is most happy sorting reverse-sorted lists, because it's fun to do that swooping motion, and then the job is done.
Comparisons to other sorting algorithms[edit]
Comparing nebula sort to other sorting algorithms is like comparing supercomputers hardwired to totally own people at "Jeopardy!" to solar-powered scientific calculators. Nebula sort is just awesome, hands-down.
The only case in which other sorting algorithms should be used is when not enough fingers are available to perform the all-at-once stuff, but that's a hardware thing, and most computers can do it nowadays.
Variants[edit]
Captain Obvious was the first to suggest the use of toes, tails, tentacles, or other appendages instead of fingers to do the sorting, as these alternatives can be more flexible, powerful, and robust.
Oscar Wilde envisioned that someday, these things would be done "in the cloud", because clouds are closer than nebulas, although they are more ephemeral, and the sluggishness of computers back in his day couldn't handle the way the vapors moved about.