One More Word on "Count Sort" versus "Parallel Sort."

One More Word on "Count Sort" versus "Parallel Sort."

[Austin Obyrne]

I have done a bit of homework on the historical development of this sort program now i.e. Count Sort and it behoves me to share the results with anybody who is still interested.

I have had a lot of friendly good advice from several readers and I can say that all of what people have said comes true but ....(almost).

Quote from Wikipedia.

Although radix sorting itself dates back far longer, counting sort, and its application to radix sorting, were both invented by Harold H. Seward in 1954.[1][4][8]   : Unquote.

The algorithm at that time cannot have been anything more than a desktop paper algorithm because computers didn’t come into vogue until the 70’s .

I followed up “Introduction to Programming – Vol 3 Sorting and Searching 1998” by Donald Knuth which is supposed to be almost a seminal work given the fame of the author but there is no mention of Count Sort in the contents so I didn’t buy the book - I had expected a discussion of Count Sort and maybe a published computer program of it.  His first edition of the book was in 1973 and given that ‘C’ and 'C++' were well established by 1998 one would have expected a published program in the ‘C’ or 'C++' programming languages in that later edition (if anybody knows of one please let me know).

A really good find was this title,

“Introduction to Algorithms”  - T. Cormen, C. Leiserson, R. Rivest,  C Stein.  I’m going for this instead – it is written in pseudo code which is very much easier to follow and it gives a lot of good mathematical proofs.

For example why is O(n Log n) the lower bound for comparison sort programs and much more that I found interetsing .


I am pleased to be able to say “It is rather neat the way my "Parallel Sort" gets the first numbers before knowing any of the others”.  It goes straight for the jugular and consigns it preemptively to its proper address in the sorted array immediately it captures a value in the variable being monitored.

The traditional "Count Sort" does not do this and although it is not a comparison sort method per se it still does require some evaluation work before indexing any element in the array - it appears to need to know what is coming next.  I see this as a stumbling block to a fully embedded sort program that can work in parallel and in current realtime with a second main program.  This is a plus for "Parallel Sort" because it does exactly that.

It happens that Ada lends itself perfectly to this design of parallel sorting program for embedding seamlessly with main programs that may contain any number of variables for sorting.

Cheers,

Austin O’ byrne.

PS – Anybody care to expanded on (nlogn) - proof?
What's the value of Ln n!(n factorial?

Also,

Any base is valid in this function.

Clearly, any base will do because the constant that accompanies a change of base is ignored in complexity theory.

Example: Log(a)n = Log(b)n / lg(b)(a)

 lg(b)(a) is a constant that is independent of 'n' and does not affect the “order” of the complexity and can be ignored => any base is valid.