BitSorting Algorithm with complexity O (n)

Prehistory

In my free time I decided to think about whether it would be possible to create a matching algorithm which would have O (n) complexity would not take up much additional memory and could be easily parallelized. And achieved some results.

Imagine that we have the following set of numbers:

• 123
• 12345
• 22345
• 12345678
• one

How are we going to sort this data array as humans? That's right, we will choose the most visually long number.
And if the length is the same, then we will compare the numbers in one bit. I thought that it was also possible to make the computer work.

Algorithm

So, we have an input array of numbers of size N:

int[] array = new int[n] 

Next, we represent each element of the array in binary form and save it in a new list:

 bool[][] bitMatrix = new bool[n][]; //    for (int i = 0; i < array.Length; i++) { BitArray bitArray = new BitArray (new int[1]{ array [i] }); bool[] bits = new bool[bitArray.Length]; bitArray.CopyTo (bits, 0); Array.Reverse (bits); bitMatrix [i] = bits; } 

We got the following matrix:

')
Then comes the most interesting part: recursive sorting.
To begin with, let's take a look at how we would sort this bit matrix:

1. We look at the first column
2. Select all items where the first bit is 1 in one list
3. Select all items where the first bit is 0 in the second list
4. Repeat steps 2 and 3 for the first and second lists, but for column number two

The code will look like this:

 private void SortAlgorithm(bool[][] bitMatrix, int columnNumber) { List<bool[]> ones = new List<bool[]> (); List<bool[]> zeros = new List<bool[]> (); for (int i = 0; i < bitMatrix.Length; i++) { if (bitMatrix[i][columnNumber]) ones.Add(bitMatrix[i]); else zeros.Add(bitMatrix[i]); } columnNumber++; if (columnNumber == MAX_COLUMN_COUNT)//MAX_COLUMN_COUNT = sizeof(int)*8 { sortedBitMatrix.AddRange(ones); sortedBitMatrix.AddRange(zeros); return; } if (ones.Count != 0) SortAlgorithm (ones.ToArray(), columnNumber); if (zeros.Count != 0) SortAlgorithm (zeros.ToArray(), columnNumber); } 

sortedBitMatrix is used to store a sorted bit matrix.
To convert the bit matrix back to an array, use the following method:

 private int[] ConvertBitMatrixToArray(List<bool[]> bitMatrix) { int[] resultArray = new int[bitMatrix.Count]; int count = 0; for (int i = 0; i < bitMatrix.Count; i++) { bool[] bits = bitMatrix [i]; Array.Reverse(bits); BitArray bitArray = new BitArray(bits); int[] tmpArray = new int[1]; bitArray.CopyTo(tmpArray, 0); resultArray [count] = tmpArray [0]; count++; } return resultArray; } 

The result of the method will be a sorted array.

But what about paralleling?

Since most of the time is spent on passing through each column of the bit matrix in the search for ones and zeros, this process can be run in several streams.
Each thread will look for ones and zeros in a part of the matrix:

Complexity

To sort a given array, we need the following iterations:

1. Creating a bit matrix: n
2. Search for zeros and ones: 32n
3. Convert sorted bit matrix: n

Total: 34n, which is O (n)

Interested in your opinion.
Thanks for attention.

PS github.com/koljaka/BitSorting