Page 1 of 1

A Possibly New Sorting Algorithm

Posted: Wed Oct 07, 2009 5:15 pm
by elendiastarman
I wrote my own sorting algorithm for one of the problems and after looking at the list of sorting algorithms on wikipedia, it looks like my algorithm has not been covered. Thing is, it's simple enough to make me believe that it should have been noticed before... I think it takes O(2) memory and about O(n log n) in terms of computation.

Anyway, the algorithm goes through the original list in sequential order and inserts them into a new list according to a rule based off of the Guessing Game (try to guess a number between x and y in fewest tries). Two bounds are updated as the algorithm progresses; the upper bound and lower bound. The upper bound starts at the length of the new list and the lower bound is 0. The "midpoint" (middle bound) of these two bounds is found and the number at that location in the new list is checked against the current number being inserted. If the midbound number is larger (or equal to) than the number being inserted, the upper bound becomes the middle bound. The lower bound is updated instead if the reverse is true. This process is repeated until the upper bound and lower bound are separated by 1, at which point the new number is inserted between those two indices. The whole process should take log2n operations where n is the length of the new list. It is my experience that this process is rather fast and can also be used to find a member of the list.

Re: A Possibly New Sorting Algorithm

Posted: Wed Oct 07, 2009 5:44 pm
by quilan
Isn't this just a binary insertion sort?

Re: A Possibly New Sorting Algorithm

Posted: Wed Oct 07, 2009 6:12 pm
by elendiastarman
I thought about that too, but the description on wikipedia uses a binary tree and I don't quite see any possible resemblance... :/

Re: A Possibly New Sorting Algorithm

Posted: Wed Oct 07, 2009 6:16 pm
by quilan
http://en.wikipedia.org/wiki/Insertion_sort#Variants discusses it briefly. This is not the same as tree sort.

Re: A Possibly New Sorting Algorithm

Posted: Wed Oct 07, 2009 7:43 pm
by elendiastarman
Indeed, that is it. I knew it couldn't have been new...