Re: My Invention of "Bug Sort".

["Peter C. Chapin" <PChapin@vtc.vsc.edu>]

On 2012-06-19 03:13, Austin Obyrne wrote:

> Copyright � 2012 Austin O'Byrne.
>
> Let us say that �NextNum� is a variable in a program output string that the user wants to sort at the end of the program run.
>
> How it works.
>
> Each change in �NextNum� is trapped as it is computed by a �bug� strategically placed in the lines of source code.
>
> Q := NextNum(I);
> I_NUM(Q):= I_NUM(Q)+1;
>
> (This is the bug)
>
> The bug �gets� (captures) the instantaneous value of NextNum as it materializes and then immediately writes this instantaneous value  to a dedicated array in order of *magnitude and returns for the next i.e. each value indexes its own place in the array ( *not in sequential order where the entries would be contiguous and remain unsorted � this is the most salient point for the reader to note).
>
>   *This is defacto sorting per se.
>
> It only needs to read back from the array to see the sorted string which can be anything up to 1 million or more elements sorted in a split second, to complete the task.

I find your style of writing difficult to understand. However, if I 
follow what you are saying, you are talking about Radix Sort. That 
sorting method is O(n) instead of O(n log(n)) (which is the best 
attainable running time for a comparison sort). However in general it 
can have huge memory requirements and is really only practical in 
special cases.

Peter