My Sorting Algorithm: Melsort

A friend challenged me to a little algorithm writing contest and I'd never written an algorithm before (this was about a year and a half ago) and had little knowledge of algorithms.

Specs:
Write code that sorts an array of numbers from lowest to highest.
Use this array: [5, 2, 8, 0, 9, 3, 1]
Don't look up sorting algorithms.

It goes without saying that I was not allowed to Ruby's built-in sort method on the array => array.sort!
That would be cheating as the point is to create the code that sorts the array.

I thought of a number of ways to do this (I had a bubble sort-like piece of code that I never finished), but the quickest code I whipped up was this:


If the code is a bit hard to read, it does this:
I have two arrays. The original array containing unsorted numbers and an empty array where the sorted numbers will go.

Starting from zero, I count up one number at a time, checking each time if the number I just counted is in my unsorted array. If it does appear in the unsorted array, I add that number to the empty array. I stop counting when both arrays area equal (contain the same elements.)

There are two major problems with this:
1.) The code is unable to sort numbers with decimals.
2.) The code would be incredibly slow if the unsorted numbers were larger. For example, if the array contained 15 and the next highest number was 1587932057693576, the algorithm would count all the numbers in between 15 and 1587932057693576 before it could tell that 1587932057693576 was the next item to appear in the sorted array.

I won the contest as my sorting algorithm sorted the array faster than my friend's code did. However, considering the above problems, his code was far superior.

Posted in: