O(N) Sort Data Structures

💡 Ideas
1

There are now neural networks powerful enough to facilitate order O(N) Sort, provided all entries are matching datatype...

Example #1

let a = new SortedUInt8Array() // cf. SortedUInt16Array SortedUInt32Array SortedUInt64Array SortedInt8Array SortedInt16Array SortedInt32Array SortedInt64Array

a.push(255)
a.push(8)
a.push(12)
a.push(7)

a /* [ 7,8,12,255 ] */
a[0] /* 7 */


Example #2

a = new SortedCharArray() // cf. SortedCharArrayUpper SortedTextArray SortedTextArrayUpper

a.push('c')
a.push('z')
a.push('e')
a.push('a')

a /* [ 'a','c','e','z' ] */
a[0] /* 'a' */
2

Did you confuse a sorting network with a neural network?

Also it's not quite clear what the array types you are suggesting would be doing exactly, and why they would need to be builtin instead of being provided by a library.

1 Like
3

Can you provide a paper? By the way, O(n) sort is already achieved using radix and counting sort, but in practice, they are not viable for sufficiently small arrays.

1 Like
4 
// A non-radix based O( N ) solution, implementing a NN global shift register
a.push( 8 ) // = 1 1 1 1  1 1 1 1
a.push( 3 ) // = 1 1 1 0  0 0 0 0
a.push( 5 ) // = 1 1 1 1  1 0 0 0 
a.push( 7 ) // = 1 1 1 1  1 1 1 0
            // Allowing 1's to the bottom of a column; and 0's to the top of a column...
            //--------------------
a[ 0 ]      // = 1 1 1 0  0 0 0 0 = 3
a[ 1 ]      // = 1 1 1 1  1 0 0 0 = 5
a[ 2 ]      // = 1 1 1 1  1 1 1 0 = 7
a[ 3 ]      // = 1 1 1 1  1 1 1 1 = 8
5

Please provide an algorithm (or a link to it) for your O(1) sorted-push method, not a random example.

1 Like
6

I did find one example (provided a known upper bound exists): https://en.wikipedia.org/wiki/Bucket_queue

Also, things like counting sort, pigeonhole sort, and bubble sort exist that provide O(n) integer sorting and those could be used to build fully constant-time integer priority queues, though this doesn't necessarily specify any particular algorithm (only a blueprint for various algorithms).

The immediate proposal here is confusing this with neural networks, though, and really needs to go back to the drawing board and take into better account existing algorithms and how they might be implemented. Also, I'm not sure why they're suggesting this be incorporated into the core language when I don't even see libraries being cited here (or cases where the language legitimately doesn't provide the facilities necessary to implement it).

1 Like