The time complexity of finding the kth smallest number using buckets

Question

I've implemented kth smallest number using buckets representing the current nibble value of each element in the array where current is a value starting possibly at 64 (for 64 bits integers at most) and decrements each iteration by 4 (nibble size).

I was wondering what is the time complexity (worst) of this implementation. I think it's O(n^log64/4) which is O(n^16), is that correct?

function nthSmallest(array, k, sizeOfInt) {
    let buckets = [
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        []
    ];
    // put numbers in buckets - O(n)
    for (let i = 0; i < array.length; i++) {
        const high = (array[i] >> sizeOfInt - 4) & 0xF; // 4 = nibble size
        buckets[high].push(array[i]);
    }
    let numbers = [];
    for (let i = 0; i < buckets.length && numbers.length < k; i++) {
        if (numbers.length === k - 1 && buckets[i].length === 1) {
            return buckets[i][0];
        }
        for (let j = 0; j < buckets[i].length; j++) {
            numbers.push(buckets[i][j]);
        }
    }
    return nthSmallest(numbers, k, sizeOfInt - 4);
}

Answer 1

Your algorithm is a variant of the radix sort.

Consider $k=n$ and the greatest two numbers differ by only the least 4 significant bits, then the two greatest numbers will be always in the last buckets in each iteration except the last. This means you have to iterate for sizeOfInt, sizeOfInt - 4, ... until 4, so the overall complexity is $O(nw)$ where $w$ is sizeOfInt.