The idea is to search for the highest number, and then to create an 2d-Array, whose length equals the highest number. Afterwards all items of the unsorted array are placed in the sorted array into the place with the index that equals their number.

So every 0 is placed into the first array of the sorted array, every 2 is placed in the third array of the sorted array, every highest number is placed in the last array of the sorted array.

In the end an array that may look like this: [[0,0],[],[1],[],[2], [4,4,4]] will be compiled into an proper 1-d array (in this case: [0,0,1,2,4,4,4]).

Here's the python code:

import time
import numpy as np

start = time.time()

def proto_sort(arr):
    highest_value = 0
    for item in arr:
        if item > highest_value:
            highest_value = item
    sorted_arr = [[]] * (highest_value + 1)
    for num in arr:
        sorted_arr[num] = sorted_arr[num] + [num]

    output_arr = [None] * len(arr)
    num = 0
    for item in sorted_arr:
        for j in item:
            if j != None:
                output_arr[num] = j
                num += 1



# Example usage
arr = []
for i in range(100):
    arr.append(np.random.randint(0, 100))
sorted_arr = proto_sort(arr)
end = time.time()
print(end - start)

However at least in my tests, counting sort is always better (I just wanted to share the idea) (Edits for clarification)