N2Sort Sorting Algorithm
Description
This page demonstrates how a very simple sorting algorithm works. This algorithm is typically called "I can't believe it can sort" but since that name is long and silly I will refer to it as n2sort. I am calling it n2sort because its time complexity is quadratic independently of the original data. This means that this algorithm is asympototically less efficient than the most widely used sorting algorithms and is probably not a good algorithm to choose in most cases. It is nonetheless interesting because it is very simple and can be written in only about 4 lines of code.
Here is a listing of the n2sort code used for this page:
This is bit more than 4 lines but some of them only contain a brace, which we wouldn't usually count as a line of code. Also line 9 only exists for display purposes and is not part of the algorithm itself.
This page displays the progress of the algorithm as an n x n matrix where n is the number of items in the list being sorted. Each row of the matrix corresponds to the permutation of the original data that is generated by one step through the outer loop of the algorithm. This allows us to get a clearer picture of how the algorithm works. Note that the diagonal element and all elements that precede it are correctly sorted in ascending order. As long as this invariant is maintained we see that the final row will be completely sorted.
It appears that this algorithm was first published by Stanley Fung in 2021 in this paper.