Weird sorts #1 — LIS sort

Weird sorts #1 — LIS sort

By diavolobia, 9 hours ago,

I like sorting algorithms very much, and I usually come up with weird ideas for sorting. Sometimes I wonder would those work properly, and now when I finally have the time from social distancing, I decided to start a series on my eccentric ideas — Weird sorts.

As an introductory problem for Dynamic Programming, you all probably know about the Longest Increasing Subsequence problem (LIS). But what if we apply this… to sorting? Today in the first blog of the Weird sorts series, I introduce to you… the LIS sort.

Basic idea

The core idea is to extract the LIS from the current array and repeat it until the current array is empty. It can be shown that this process always terminates, because there will always be a LIS that have a size of at least 1, thus at each pass, we will always take at least 1 element away from the array. In the implementation, we will first find the LIS of the array and separate the LIS from the rest of the array. We will then recursively perform the LIS sort on the remaining items, and merge them with the LIS using the same technique in Merge sort. The pseudocode looks something like this:

For better understanding, see this animation. The flaw of this algorithm lies in the number of passes that it must perform. In the worst case, the array will be in a non-decreasing order, requiring N passes to completely empty the array. Assuming you are using the standard way of finding LIS, each pass will cost O(N2)O(N2), making the total complexity of this algorithm O(N3)O(N3). Below are the tables of runtime with different types of arrays.

Optimization 1

The most time-consuming part of the sort is the step where we are looking for the LIS, which costs O(N2)O(N2), so we should start optimizing from there. For optimizing the LIS problem from O(N2)O(N2) to O(N∗logN)O(N∗log⁡N), there have been many pages and articles written about this, so you should look them up for yourself. Here’s my favorite site: link.

Other than that, the rest of the code is the same. By reducing the cost of finding LIS from O(N2)O(N2) down to O(N∗logN)O(N∗log⁡⁡N), we have reduced the worst-case complexity of the sort from O(N3)O(N3) to O(N2∗logN)O(N2∗log⁡⁡N). Again, here are the tables of runtime with different types of arrays.

Optimization 2

In the last 2 tests we can see that the sort performs exceptionally bad when it comes to descending arrays and arrays with equal elements. Also, when a LIS is taken from an array, there are high chances that the remaining items will form a non-increasing subsequence (this isn’t always the case, however). So, by reversing the remaining array, we increase the chance of more items being taken away from it in the next pass, thus improving the runtime of the average case and the case where the array is decreasing. Here are the tables of runtime with different types of arrays.

Optimization 3

You may realize that it still performs pretty bad in the case where the array contains equal elements. It’s easy to fix this, however: instead of finding the longest increasing subsequence, we will find the longest non-decreasing subsequence. This makes sure that all equal elements are covered in one pass. Surprisingly, this even lowers the upper bound of the number of passes the sort needs to do.

How? Well first, let’s call the number of increasing subsequences is AA and length of the shortest one is BB. Because the array is reversed on each pass, so either the longest increasing subsequence or an element of every other increasing subsequence is taken. Therefore, the last subsequence we take will be the shortest one (providing we didn’t take all of its elements before), so the number of passes should be min(A,B)min(A,B).

Now we will try to generate an array that maximizes min(A,B)min(A,B), which is basically the worst case. First, let’s fix the value of AA and maximize BB based on AA. We have:

N=L1+L2+...+LAN=L1+L2+...+LA

In the above equation, LiLi denotes for the length of the ithith increasing subsequence. For some kk, let LkLk be the length of the shortest increasing subsequence. We will have:
ㅤ

Lk≤Li(∀i∈[1,N])⇒L1+L2+...+LA≥Lk+Lk+Lk(A times)⇒N≥A∗Lk⇒N≥A∗BLk≤Li(∀i∈[1,N])⇒L1+L2+...+LA≥Lk+Lk+Lk(A times)⇒N≥A∗Lk⇒N≥A∗B

So, when B is maximized, N=A∗BN=A∗B. From the equation we just deducted, we can show that the upper bound of min(A,B)min(A,B) is N−−√N. To prove it, let’s assume that min(A,B)>N−−√min⁡(A,B)>N.
ㅤ

⇒min(A,B)>A∗B−−−−−√⇒min(A,B)∗min(A,B)>A∗B⇒min(A,B)∗min(A,B)>min(A,B)∗max(A,B)⇒min(A,B)>max(A,B)⇒Impossible⇒min(A,B)>A∗B⇒min(A,B)∗min(A,B)>A∗B⇒min(A,B)∗min(A,B)>min(A,B)∗max(A,B)⇒min(A,B)>max(A,B)⇒Impossible

Hence, in the worst case, min(A,B)=Nmin(A,B)=N. Since we need 1 pass to take the longest subsequence and 1 extra pass to take the first element of every other subsequence, the number of passes will never exceed 2N−−√2N. So, the time complexity of this sorting algorithm is O(NN−−√∗logN)O(NN∗log⁡⁡N). Of course, that’s just all the theory, let’s see how this optimization actually performs in benchmarks. Here are the tables of runtime with different types of arrays.

Since it performs pretty good even in edge cases, let’s put it against the real pros on the battle. Here’s the table of runtime with the LIS sort and various other sorts on random arrays.

While it was much faster than its unoptimized variants, it’s having a hard time trying to keep up with other sorts. This is due to the extra O(N−−√)O(N) cost of processing different passes, compared to other sorts that perform only in O(N∗logN)O(N∗log⁡⁡N).

Technical details

All tests in this blog are benchmarked with an i7-1165G7 running at 3.30 GHz with 16 GB of RAM. All numbers were randomly and uniformly generated in the range [1,106][1,106] using the testlib.h library (source). Execution time was measured in seconds. The codes were executed on CodeBlocks 20.03 using C++14 and Release build target. Tests were repeated 20 times and the final value was taken from the average of 20 values.

Here are all the source codes I used to benchmark: link

Summary

To be honest, I don’t think there are any practical uses of this sort. There are many other sorting algorithms that are both faster, and more memory efficient. However, I did learn a lot while doing research and looking for proofs, especially about inequalities.

Special thanks to trnthienphc2003 and algo_4_life who helped me with the proofs, and to my friends who proofread this blog. Also this is the first time I write such a long blog, so mistakes are inevitable. Please comment about logical errors or grammar mistakes if you find any, or just share your thought. Thank you all for reading my little blog.