The story behind oyvindSort()

As I'm quite new to Steemit, I was recommended to write an introduce yourself post, but as I consider myself somewhat of a litterature enthusiast, I have a fondness for the idea that it's better to show than to tell.

Anyways, this is where most Steemians (?) would start to tell something interesting about themselves. Instead, I will tell the story about the sorting algorithm which bears my name, for the simple reason that I believe it shows a curious part of my persona.

It's the sixth of June, 2016. The rain is pouring down, making m question why I'm walking aimlessly around along the western coast of Norway. My view was quite similar to the picture below:

At this point I you're probably asking what this has to do with anything. Well, I'm glad you asked. I was while sitting in the car of which destination I have already described that my thoughts wandered back to what I might have learnt during a class in object oriented programming.

You would — as an uninformed reader, that is — assume that I might actually rather have learnt what I have yet to tell you, in my Algorithm course, which I did. I did, however, not have an Algorithms course until the year after. It should be noted that when I learnt what you as a reader do not yet know — unless you're reading this post for the second time, in which case you're not an uninformed reader, so your argument is invalid — is not relevant to the story. By the way, here is a picture to prove that it did indeed rain:

Anyways, what rain told me at that brainy day... wait, what? I meant to say that the other way around...

Or did I?

"It's impossible to sort elements in linear time" That was what I remembered, or thought I remembered. Of course, given certain conditions, linear time sorting is of course possible, but I didn't learn this until a year later, so I was still pretty much an unfished fish.

As you should be able to tell by now, this was indeed a brainy day, and it was the rain falling from the sky, which fueled my thoughts with ideas which over the next year would bring over 45 (46, that is) sorting enthusiasts to my humble oyvindSort() facebook group.

It occured to me that if the raindrops had different mass, but the same shape, the raindrops with the heavier mass would hit the ground before the ones less fortunate. Of course, this would require a certain height, so that heavy raindrops which were falling from far above the lighter raindrops would have time to pass them on their way down.

In short: oyvindSort calculates the shortest height obtainable without comparisons, which guarantees that no raindrops land in the wrong order or at the same time.

Or does it?

The algorithm itself actually just calculates the position each falling raindrop at the time when they have just fallen long enough to be guaranteed to be in sorted order with no overlap. In that sense it does not calculate the needed height explicitly. It just uses it, if that makes sense.

The algorithm:
In a list of n elements where k is the largest number and the n elements of value v are located in position i=0, 1, 2, 3,... n-1, the sorted position of each individual element is given by v*k+i. That's oyvindSort() in its simplest form. It returns a list of n sorted elements in linear time. There are, however, a few drawbacks.

1. This only works for integers.
2. Just returning a list of the new position of the elements requires O(n) memory, but returning the actual list, including the empty spaces requires O(n*k) memory.
3. There are empty spaces in the list.

In my implementation of oyvindSort(), I just iterated through the sorted list and removed the spaces, saying goodbye to my linear runtime, rather settling for a pseudolinear runtime. In my head this seemed okay, since in most larger sets of values in the real world have an upper bound.

Or so I thought...

I didn't have statistics until the year after, so forgive me for my reckless assumptions.

With a fresh new sorting algorithm, I felt a need to share my discovery (surely a less effective counting sort must count as a discovery?). It was a late night, on October 6. 2016 (okay, by this time oyvindSort() wasn't fresh and new anymore) that I made the oyvindSort() Facebook group. My initial intention was to make a Facebook page, but for some reason Facebook doesn't allow parentheses in page titles. Have I mentioned that I'm not the biggest fan of Facebook? I'm not the biggest fan of Facebook, and I do not mean that as an understatement. I don't dislike it. I'm just frightened by the thought of having so much authority stored in one place. Well not really.

Where was I? Oh, the oyvindSort() Facebook group. I had my roommate make an epic illustration of the fundamentals of oyvindSort() in Paint, the process of which can be admired in the picture below:

After more than 30 minutes, we sat in our couch admiring what would be the header image for the Facebook group. The illustration was beautifully simple, hard to understand and also incorrect, but in our tired excitement, we didn't notice any of this until a few days later and then our inspiration was imaginary at best. I have included the finished illustration below:

The text might be hard to read, but it's incorrect, so it's probably for the best. Also, the element of value 2 is supposed to be placed one place to the left. The important thing is that none of this mattered. The group was a huge success, perhaps because Facebook allows you to add people to groups without their consent. Did I mention that I'm not the biggest fan of Facebook?

You might wonder what gets posted in a sorting algorithm Facebook group. Well, so did I. Using what was left of my brain, I decided to post some oyvindSort() memes, some of which I have included below:

As you can see, I didn't quite understand memes at that point. I just placed text on random memes, totally ignorant of any established meme rules or whatever the guys at 9gag see as the greater good. Have I mentioned that I'm not the biggest fan of 9gag? I'm not the biggest fan of 9gag, and I do mean that as an understatement.

After having told my closest friends about my Facebook group and they had told their closest friends about my Facebook group and their friends had told their friends about my Facebook group, my sorting community grew rapidly and I suddenly realized that people whom I had not yet met recognized me because of my algorithm. People were even starting to use oyvindSort() as their nickname during the Kahoot quizes in Algorithms class:

As can be seen from the image, oyvindSort() is superior to bubble sort.

I programmed some sample tests of oyvindSort() in Java on the JVM compiler app on my iPhone. The images below show how the runtime is linear for a constant upper bound k:

If the upper bound k increases (similar to n in this example), the runtime is no longer O(n), but O(n*k), as shown in the images below:

The oyvindSort() Facebook group was active for about a year, after which it was kind of forgotten. I actually sold some t-shirts with the oyvindSort() logo:





I also started making car-themed t-shirts, which would later lay the foundation for Differ Clothing, but that's a story for another time.

I'm not sure as to how this post served as a good introduction. I feel that I went way off topic, but so did oyvindSort(), so I guess, me writing is quite brilliant after all. If you want to send me free Bitcoin, feel free:

1BmeGvmdav9KGggJphe4cKko7qWpnPcGTD