So Who is Credited with Inventing “Count Sort” as we know it Today - Anybody?

So Who is Credited with Inventing “Count Sort” as we know it Today - Anybody?

[Austin Obyrne]

I volunteered to draw a line under this topic last evening but on refection I don’t think I should roll over that easily without making a claim to at least re-inventing a close resemblance and perhaps an improved version of that same sort program. 

I am continuing my claim to have invented a sort program that I am calling “Parallel Sort”.

Digressing for a while, Charles Babbage (born 1791) is famously credited with breaking the equally famous “Vigenere Cipher” that had lain unbroken for two centuries prior to that.  His modus operandi was based on his noticing that languages have a frequency pattern. 

In cryptography, if the ciphertext is the same data type as the plaintext it is obfuscating, the illegal cryptanalyst can establish the frequency of the ciphertext and then use this to statistical map the ciphertext in an exploratory way to the plaintext that it originated from. (This statement is hugely over simplistic here) 

That was the ploy that Babbage invented.

The Brits are usually fairly honest people about such matters and give credit where credit is due.  The Russian, Friedrich Wilhelm Kasiski  had beaten Charles Babbage to this invention however  by ten years and it is conceded therefore today that it is a joint invention by both Kasiski and Babbage at different times.

Sorting and checking for repeats is an important process in cryptography to day and a sort program such as I am using is deserving of its place in the history of crypto technology in my view.

I shall continue therefore to claim my invention of Parallel Sort (Like Babbage) is an independent piece of intellectual property.

But who did invent “Count Sort” on the other hand is something I would like to know – an individual ?.

Thanks again for all your helpful comments.

Austin O’Byrne.

Re: So Who is Credited with Inventing “Count Sort” as we know it Today - Anybody?

[Austin Obyrne]

On Sunday, June 24, 2012 2:26:27 PM UTC+1, Austin Obyrne wrote:
> I volunteered to draw a line under this topic last evening but on refection I don’t think I should roll over that easily without making a claim to at least re-inventing a close resemblance and perhaps an improved version of that same sort program. 
> 
> I am continuing my claim to have invented a sort program that I am calling “Parallel Sort”.
> 
> Digressing for a while, Charles Babbage (born 1791) is famously credited with breaking the equally famous “Vigenere Cipher” that had lain unbroken for two centuries prior to that.  His modus operandi was based on his noticing that languages have a frequency pattern. 
> 
> In cryptography, if the ciphertext is the same data type as the plaintext it is obfuscating, the illegal cryptanalyst can establish the frequency of the ciphertext and then use this to statistical map the ciphertext in an exploratory way to the plaintext that it originated from. (This statement is hugely over simplistic here) 
> 
> That was the ploy that Babbage invented.
> 
> The Brits are usually fairly honest people about such matters and give credit where credit is due.  The Russian, Friedrich Wilhelm Kasiski  had beaten Charles Babbage to this invention however  by ten years and it is conceded therefore today that it is a joint invention by both Kasiski and Babbage at different times.
> 
> Sorting and checking for repeats is an important process in cryptography to day and a sort program such as I am using is deserving of its place in the history of crypto technology in my view.
> 
> I shall continue therefore to claim my invention of Parallel Sort (Like Babbage) is an independent piece of intellectual property.
> 
> But who did invent “Count Sort” on the other hand is something I would like to know – an individual ?.
> 
> Thanks again for all your helpful comments.
> 
> Austin O’Byrne.

Harold H. Seward was a computer scientist and the developer of the radix sort algorithm in 1954 at MIT.[1] He also developed the counting sort.

I have just noticed this in Wikipedia.

Clearly, since computer science din't come into vogue until the seventies his invention must have been desk top only in 1954 - my invention emanates from  a working program in 2012 that is computer intensive - my claim that I have invented a similar algorithm but a different implementation is perfectly valid.

- adacrypt

Re: So Who is Credited with Inventing “Count Sort” as we know it Today - Anybody?

[Georg Bauhaus]

On 24.06.12 15:26, Austin Obyrne wrote:

> But who did invent �Count Sort� on the other hand is something I would like to know � an individual ?.

A standard reference for answering this question would be
Knuth, Donald E. (1998): The Art of Computer Programming,
Vol. 3, Sorting and Searching, 2nd Ed.

Chances are that classifications and names of all sorts of
sorting procedures are covered in Chapter 5, on "Sorting"
(which has 391 pages).

A  table of contents is here,

http://www.amazon.co.uk/gp/product/toc/0201896850/ref=dp_toc?ie=UTF8&n=266239

In particular, section 5.2, titled "Internal Sorting",
has a subsection  "Sorting by Counting". If this is it,
Knuth (as in every subsection) collects historical records
of first mentions of the methods at the end of the subsection.
In this case,

"Sorting by comparison counting (...) was first mentioned in
print by E.H. Friend [JACM 3 (1956), 152], although he didn't
claim it as his own invention. Distribution sorting (...) was
first developed by H. Seward in 1954 for use with radix sorting
techniques".

Re: So Who is Credited with Inventing “Count Sort” as we know it Today - Anybody?

[Austin Obyrne]

On Sunday, June 24, 2012 3:39:47 PM UTC+1, Georg Bauhaus wrote:
> On 24.06.12 15:26, Austin Obyrne wrote:
> 
> > But who did invent “Count Sort” on the other hand is something I would like to know – an individual ?.
> 
> A standard reference for answering this question would be
> Knuth, Donald E. (1998): The Art of Computer Programming,
> Vol. 3, Sorting and Searching, 2nd Ed.
> 
> Chances are that classifications and names of all sorts of
> sorting procedures are covered in Chapter 5, on "Sorting"
> (which has 391 pages).
> 
> A  table of contents is here,
> 
> http://www.amazon.co.uk/gp/product/toc/0201896850/ref=dp_toc?ie=UTF8&n=266239
> 
> In particular, section 5.2, titled "Internal Sorting",
> has a subsection  "Sorting by Counting". If this is it,
> Knuth (as in every subsection) collects historical records
> of first mentions of the methods at the end of the subsection.
> In this case,
> 
> "Sorting by comparison counting (...) was first mentioned in
> print by E.H. Friend [JACM 3 (1956), 152], although he didn't
> claim it as his own invention. Distribution sorting (...) was
> first developed by H. Seward in 1954 for use with radix sorting
> techniques".

Hi Georg,

Many thanks for this information - Iwas able to locate a used copy in "BetterWorldBooks" for only £6-50.

His first edition was in 1973 and Ada was first published as Ada-83 in 1983 so it is probable that the algorithm may have been used in some computer language some over the last 30 years.

It is not desperately important but I would like to be able to say that my implementation is the first in Ada and is completely independent of the algorithm in 1954 by H. Seaward (hope I've got the name right).

The book might say if there is an implementation in 'C' that I can view just to compare with my own.

Very grateful,

Austin O'Byrne.

Re: So Who is Credited with Inventing “Count Sort” as we know it Today - Anybody?

[Jeffrey Carter]

On 06/24/2012 10:08 AM, Austin Obyrne wrote:
>
> His first edition was in 1973 and Ada was first published as Ada-83 in 1983
> so it is probable that the algorithm may have been used in some computer
> language some over the last 30 years.

MIL-STD-1815, 1980 Dec (Ada 80).

-- 
Jeff Carter
"When danger reared its ugly head, he bravely
turned his tail and fled."
Monty Python and the Holy Grail
60



--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

Re: So Who is Credited with Inventing “Count Sort” as we know it Today - Anybody?

[Austin Obyrne]

On Monday, June 25, 2012 5:06:19 AM UTC+1, Dennis Lee Bieber wrote:
> On Sun, 24 Jun 2012 10:08:50 -0700 (PDT), Austin Obyrne
> <austin.obyrne@hotmail.com> declaimed the following in comp.lang.ada:
> 
> 
> > It is not desperately important but I would like to be able to say that my implementation is the first in Ada and is completely independent of the algorithm in 1954 by H. Seaward (hope I've got the name right).
> >
> 	You need to take into account that "algorithm" basically means
> "recipe".
> 
> 	You are trying to emphasize that you baked (implementation) a loaf
> of bread using an electrically heated steel-wall oven using a recipe
> (algorithm) that was first baked (different implementation) using a
> wood-fired stone/clay walled oven. At best, you can claim that your
> "sour-dough starter" is different from the starter used by the bakery
> down the street -- but they both produce "sour-dough" loaves.
> 
> 	Implementing a known algorithm/recipe in a particular programming
> language doesn't earn any special credit. You would need to demonstrate
> that the language-independent algorithm itself is different to really
> gain credit.
> -- 
> 	Wulfraed                 Dennis Lee Bieber         AF6VN
>         wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

Yes - you are quite right.

Austin.

Re: So Who is Credited with Inventing “Count Sort” as we know it Today - Anybody?

[Simon Wright]

Dennis Lee Bieber <wlfraed@ix.netcom.com> writes:

> 	Implementing a known algorithm/recipe in a particular programming
> language doesn't earn any special credit. You would need to demonstrate
> that the language-independent algorithm itself is different to really
> gain credit.

I don't know: Austin did invent it, he just wasn't the first.