an optimized version of the hilbert sort algorithm.

hilbertSort.py

def hilbert_sort(data):
    """
    Sorts an input array using Hilbert curve mapping.

    Parameters:
    data (list): The input array to be sorted.

    Returns:
    sorted_data (list): The sorted input array.
    """
    # Step 1: Convert each number to binary using zfill to ensure each binary string is 16 bits long
    binary_array = []
    for n in data:
        binary_array.append([int(b) for b in bin(n)[2:].zfill(16)])

    # Step 2: Generate the coordinates for each binary string using the Hilbert curve
    coords_array = [[0, 0] for _ in range(len(data))]
    mask = 0b1000000000000000
    for i in range(15, -1, -1):
        mask >>= 1
        bit = [(n & mask) != 0 for n in data]
        if i % 2 == 0:
            coords_array = [[coords_array[j][0], coords_array[j][1] | (bit[j] << i//2)] for j in range(len(data))]
        else:
            coords_array = [[coords_array[j][0] | (bit[j] << (i-1)//2), coords_array[j][1]] for j in range(len(data))]

    # Step 3: Sort the data array based on the Hilbert curve coordinates
    sorted_indices = sorted(range(len(data)), key=lambda i: (coords_array[i][1], coords_array[i][0], i))
    sorted_data = [data[i] for i in sorted_indices]

    return sorted_data[::-1]

if __name__ == "__main__":
    # Test the sorting function
    import random
    input_data = [random.randint(1, 10) for _ in range(10000)]
    sorted_data = hilbert_sort(input_data)

    print("input:", input_data)
    print("sorted:", sorted_data)