Creative sorting algorithm?

Question

I just wanted to know if there are any sorting algorithms that are as interesting as Bogosort to sort a pack of cards.

Use your creativity.

For a change efficiency ain't important but being creative is :)

Answer 1

Iterate over the values to find the lowest. Now iterate again outputing a single value for every value the matches the lowest (including itself) Repeat, except that now find the minimum above the previous minimum. Continue until no such value is found.

O(n^2)

Answer 2

I came up with a sort that determines the first item as quickly as possible (N-1 comparisons), then the second (lgN steps), and tries to do likewise for the rest. The book-keeping is excessive, but the number of comparisons ended up being less than quicksort for 1,000,000 items (the largest data set I tested).

Answer 3

Ontological sort. (Assumes multiple universe theory is correct.) Properties:
- O(n) space and time
- in-place
- general purpose

1. Randomly permute input.  (O(n).)
2. Check that the sequence is sorted.  (O(n).)
3. If sequence not sorted, destroy universe. (O(1).)

Step 3 isn't implemented in version 1.