A Possibly New Sorting Algorithm

Mechanics, discrete, statistics, ...
Post Reply
User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

A Possibly New Sorting Algorithm

Post by elendiastarman » Wed Oct 07, 2009 5:15 pm

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.
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: A Possibly New Sorting Algorithm

Post by quilan » Wed Oct 07, 2009 5:44 pm

Isn't this just a binary insertion sort?
ex ~100%'er... until the gf came along.
Image

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: A Possibly New Sorting Algorithm

Post by elendiastarman » Wed Oct 07, 2009 6:12 pm

I thought about that too, but the description on wikipedia uses a binary tree and I don't quite see any possible resemblance... :/
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: A Possibly New Sorting Algorithm

Post by quilan » Wed Oct 07, 2009 6:16 pm

http://en.wikipedia.org/wiki/Insertion_sort#Variants discusses it briefly. This is not the same as tree sort.
ex ~100%'er... until the gf came along.
Image

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: A Possibly New Sorting Algorithm

Post by elendiastarman » Wed Oct 07, 2009 7:43 pm

Indeed, that is it. I knew it couldn't have been new...
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

Post Reply