More on the “Parallel Sort” Data Sorting Program.

More on the “Parallel Sort” Data Sorting Program.

[Austin Obyrne]

I am promoting this as a re-invention of “Counting Sort” having being acquainted of the latter’s existence by readers, something I was truly unaware of but would like to point out that “Counting “ or “Count sort” was invented in 1954.

I 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.”  - Unquote       


Given the state of progress in computer development at that time this invention must surely have been more of a longhand algorithm than a computer driven program concept.

I am not an an ego-trip here but I think it’s fair to say that my implementation of “Parallel Sort” as a data sorting program written in Ada is a quite different invention.

Given that the algorithm is unique and cannot possibly be presented in some identical but different form (similar to the distinctiveness of the factoring algorithm which is also a benchmark in computing)) I am claiming that this is a bench mark for future in data sorting techniques that might even be used as a yardstick in comparing computer and language combinations.

I know that personally, I have supreme confidence that this is true of Ada.

In the course of updating my background knowledge, I made a few ‘almost’ right but not totally right statements that I would like to amend here just in case.

In the general macro study of complexity theory the highest order of a function is taken as the Big O rating and the minor terms including constants are ignored.

This is not true in data sorting theory – the constants cannot be ignored.

Example.

I have said,

1) In the expression (n Lg n) for the ‘worst case’ scenario datum in comparison type sort methods, any base will be acceptable and, 

2) Log(a) n = Log (b) n /Log(b) (a) – the constant Log(b)(a) can be ignored.

These are both wrong statements in data sort theory, only (n Ln n) is correct and if it is changed to a different base (pointless really) then the constant must be included.

Example:

Comparing my “Parallel Sort” data sort program that has linear complexity growth with ‘n’ increasing, to a comparison-based sort program as a ratio of these two would be, 

n; (n ln n) 
or,
1; (Ln n)

It would be totally worng if I was to instead say,

1; Log(b)(n)

Clearly, changing the base of the logarithm without including the constant of change would be wrong.

Suppose I substituted,
(Ln(n)) = (Log (b)(n) / log (b)(e) 

as shown it  would give a totally wrong comparison ratio not to include the constant (Log(b)(e))

I contend also that this is the first implementation in any computer language of any version of “Counting Sort) ever.

I am mooting my invention of “Parallel Sort” as a benchmark for future i.e. “Parallel Sort” in Ada is both a first in data sorting and a first in any computer language. 

I have written a few specimen comparison programs in Ada just for the hell of it and there is such a great amount of user assistance by way of conditional statements required in the source code that there is no case whatever that can be argued for retaining these in the future - they are just totally redundant.

It is time to move forward in another area of computational mathematics in my view away from comparison sorting methods – they are no longer required.

Austin O’Byrne,

Re: More on the “Parallel Sort” Data Sorting Program.

[Brian Drummond]

On Tue, 03 Jul 2012 04:22:43 -0700, Austin Obyrne wrote:

> I ... would like to point out that “Counting “ or “Count sort”
> was invented in 1954.
> 
> I 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.”  - Unquote
> 
> Given the state of progress in computer development at that time this
> invention must surely have been more of a longhand algorithm than a
> computer driven program concept.

What do you mean by this? Certainly not that he couldn't have implemented 
it and run it on real hardware. Wikipedia places him at MIT where he had 
access to a computer for three years by 1954.

- Brian

Re: More on the “Parallel Sort” Data Sorting Program.

[Austin Obyrne]

On Tuesday, July 3, 2012 3:43:25 PM UTC+1, Brian Drummond wrote:
> On Tue, 03 Jul 2012 04:22:43 -0700, Austin Obyrne wrote:
> 
> > I ... would like to point out that “Counting “ or “Count sort”
> > was invented in 1954.
> > 
> > I 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.”  - Unquote
> > 
> > Given the state of progress in computer development at that time this
> > invention must surely have been more of a longhand algorithm than a
> > computer driven program concept.
> 
> What do you mean by this? Certainly not that he couldn't have implemented 
> it and run it on real hardware. Wikipedia places him at MIT where he had 
> access to a computer for three years by 1954.
> 
> - Brian

Yes, I agree with that.

Nothing less than the dynamics of computer computations would have inspired him to invent his sort method that indexed arrays according to magnitude.
“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]    “ 
Looking at this quote again,  I hazard a guess that with this man’s serendipity and extraordinary intelligence he saw the enormous potential of computing a la 1954 albeit he was probably working in assembly language.  The quote herewith suggests that he was interested in sorting data for a long time prior to inventing “Counting Sort”.  He was a part of the space program also and did work for them on instrumentation.  Further guesses by me is that he never implemented “Counting Sort “ as a working program in any of the low level languages when these came along later.
Maybe the archives of MIT may have something  (In passing, he died only recently  – 19th June 2012 - RIP.)

I claim that there is no evidence of any up and running software in a modern language anywhere in the market place in recent times that uses his algorithm.  I am claiming that my implementation in Ada-95 is the first ever.

I will be quite happy to be proved wrong but it is a case of delivery – let me see it advertised or officially recorded in recent times before I will believe it.

Many thanks for your input.

Cheers – Austin. 

Re: More on the “Parallel Sort” Data Sorting Program.

[Austin Obyrne]

On Tuesday, July 3, 2012 12:22:43 PM UTC+1, Austin Obyrne wrote:
> I am promoting this as a re-invention of “Counting Sort” having being acquainted of the latter’s existence by readers, something I was truly unaware of but would like to point out that “Counting “ or “Count sort” was invented in 1954.
> 
> I 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.”  - Unquote       
> 
> 
> Given the state of progress in computer development at that time this invention must surely have been more of a longhand algorithm than a computer driven program concept.
> 
> I am not an an ego-trip here but I think it’s fair to say that my implementation of “Parallel Sort” as a data sorting program written in Ada is a quite different invention.
> 
> Given that the algorithm is unique and cannot possibly be presented in some identical but different form (similar to the distinctiveness of the factoring algorithm which is also a benchmark in computing)) I am claiming that this is a bench mark for future in data sorting techniques that might even be used as a yardstick in comparing computer and language combinations.
> 
> I know that personally, I have supreme confidence that this is true of Ada.
> 
> In the course of updating my background knowledge, I made a few ‘almost’ right but not totally right statements that I would like to amend here just in case.
> 
> In the general macro study of complexity theory the highest order of a function is taken as the Big O rating and the minor terms including constants are ignored.
> 
> This is not true in data sorting theory – the constants cannot be ignored.
> 
> Example.
> 
> I have said,
> 
> 1) In the expression (n Lg n) for the ‘worst case’ scenario datum in comparison type sort methods, any base will be acceptable and, 
> 
> 2) Log(a) n = Log (b) n /Log(b) (a) – the constant Log(b)(a) can be ignored.
> 
> These are both wrong statements in data sort theory, only (n Ln n) is correct and if it is changed to a different base (pointless really) then the constant must be included.
> 
> Example:
> 
> Comparing my “Parallel Sort” data sort program that has linear complexity growth with ‘n’ increasing, to a comparison-based sort program as a ratio of these two would be, 
> 
> n; (n ln n) 
> or,
> 1; (Ln n)
> 
> It would be totally worng if I was to instead say,
> 
> 1; Log(b)(n)
> 
> Clearly, changing the base of the logarithm without including the constant of change would be wrong.
> 
> Suppose I substituted,
> (Ln(n)) = (Log (b)(n) / log (b)(e) 
> 
> as shown it  would give a totally wrong comparison ratio not to include the constant (Log(b)(e))
> 
> I contend also that this is the first implementation in any computer language of any version of “Counting Sort) ever.
> 
> I am mooting my invention of “Parallel Sort” as a benchmark for future i.e. “Parallel Sort” in Ada is both a first in data sorting and a first in any computer language. 
> 
> I have written a few specimen comparison programs in Ada just for the hell of it and there is such a great amount of user assistance by way of conditional statements required in the source code that there is no case whatever that can be argued for retaining these in the future - they are just totally redundant.
> 
> It is time to move forward in another area of computational mathematics in my view away from comparison sorting methods – they are no longer required.
> 
> Austin O’Byrne,

Example. 

I have said, 

1) In the expression (n Lg n) for the ‘worst case’ scenario datum in comparison type sort methods, any base will be acceptable and, 

2) Log(a) n = Log (b) n /Log(b) (a) – the constant Log(b)(a) can be ignored. 

These are both wrong statements in data sort theory, only (n Ln n) is correct and if it is changed to a different base (pointless really) then the constant must be included. 

Example: 

Comparing my “Parallel Sort” data sort program that has linear complexity growth with ‘n’ increasing, to a comparison-based sort program as a ratio of these two would be, 

n; (n ln n) 
or, 
1; (Ln n) 

It would be totally worng if I was to instead say, 

1; Log(b)(n) 

Clearly, changing the base of the logarithm without including the constant of change would be wrong. 

Suppose I substituted, 
(Ln(n)) = (Log (b)(n) / log (b)(e) 

as shown it  would give a totally wrong comparison ratio not to include the constant (Log(b)(e)) 

Correction.

Humblest apologies.

<Example. 

<I have said, 

<1) In the expression (n Lg n) for the ‘worst case’ scenario datum in comparison type sort methods, any base will be acceptable and, 

<2) Log(a) n = Log (b) n /Log(b) (a) – the constant Log(b)(a) can be ignored. 

<These are both wrong statements in data sort theory, only (n Ln n) is correct <and if it is changed to a different base (pointless really) then the constant <must be included. 

<Example: 

<Comparing my “Parallel Sort” data sort program that has linear complexity <growth with ‘n’ increasing, to a comparison-based sort program as a ratio of <these two would be, 

<n; (n ln n) 
or, 
<1; (Ln n) 

<It would be totally worng if I was to instead say, 

<1; Log(b)(n) 

<Clearly, changing the base of the logarithm without including the constant of <change would be wrong. 

<Suppose I substituted, 
<(Ln(n)) = (Log (b)(n) / log (b)(e) 

<as shown it  would give a totally wrong comparison ratio not to include the <constant (Log(b)(e)) 

*This is hogwash.

I have just realised that Lg in (n lg n ) is always the binary logarithm log base 2 and there is no question of changing it.

so the ratio of "Parallel Sort" to "Comparison Sort" in terms of complexity growth is ,

1; (lg n) where lg is log(base2)and 'n' is the number of items being sorted.

Sorry about that.

Austin O'Byrne