Benchmark: radix sort each base

radix sort each base (version: 5)

radix sort base with binary number, octal number, decimal number, hexadecimal, quater of int, half of int

Comparing performance of: base 2 vs base 8 vs base 10 vs base 16 vs base 256 (2^8) vs base 512 (2^9) vs base 1024 (2^10) vs base 2048 (2^11) vs base 4096 (2^12) vs base 8192 (2^13) vs base 16384 (2^14) vs base 32768 (2^15) vs base 65536 (2^16)

Created: one year ago by: Registered User

Jump to the latest result

Script Preparation code:

function radixSort(arr, base = 10) {
    const logBase = (n, base = Math.E) => Math.log(n) / Math.log(base)
    const getDigit = (num, i) => Math.floor(Math.abs(num) / Math.pow(base, i)) % base
    const digitCount = (num) => num === 0 ? 1 : Math.floor(logBase(Math.abs(num), base)) + 1
    const  mostDigits = (nums) => nums.reduce((ret, val) => Math.max(ret, digitCount(val)), 0)

    const maxDigitCount = mostDigits(arr)

    for (let k = 0; k < maxDigitCount; k++) {
        let digitBuckts = Array.from({
            length: base
        }, () => [])

        for (let i = 0; i < arr.length; i++) {
            digitBuckts[getDigit(arr[i], k)].push(arr[i])
        }

        arr = [].concat(...digitBuckts)
    }

    return arr
}

const arr = Array.from({
    length: 10000
}, () => Math.floor(Math.random() * 10_000_000_000_000))

Tests:

base 2
const x = radixSort(arr, 2)
base 8
const x = radixSort(arr, 8)
base 10
const x = radixSort(arr, 10)
base 16
const x = radixSort(arr, 16)
base 256 (2^8)
const x = radixSort(arr, 256)
base 512 (2^9)
const x = radixSort(arr, 512)
base 1024 (2^10)
const x = radixSort(arr, 1024)
base 2048 (2^11)
const x = radixSort(arr, 2048)
base 4096 (2^12)
const x = radixSort(arr, 4096)
base 8192 (2^13)
const x = radixSort(arr, 8192)
base 16384 (2^14)
const x = radixSort(arr, 16384)
base 32768 (2^15)
const x = radixSort(arr, 32768)
base 65536 (2^16)
const x = radixSort(arr, 65536)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
base 2
base 8
base 10
base 16
base 256 (2^8)
base 512 (2^9)
base 1024 (2^10)
base 2048 (2^11)
base 4096 (2^12)
base 8192 (2^13)
base 16384 (2^14)
base 32768 (2^15)
base 65536 (2^16)

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36

Browser/OS: Chrome 131 on Windows

View result in a separate tab

Test name	Executions per second
base 2	19.5 Ops/sec
base 8	61.4 Ops/sec
base 10	71.5 Ops/sec
base 16	87.8 Ops/sec
base 256 (2^8)	185.6 Ops/sec
base 512 (2^9)	232.2 Ops/sec
base 1024 (2^10)	220.8 Ops/sec
base 2048 (2^11)	272.4 Ops/sec
base 4096 (2^12)	221.3 Ops/sec
base 8192 (2^13)	160.3 Ops/sec
base 16384 (2^14)	106.9 Ops/sec
base 32768 (2^15)	86.6 Ops/sec
base 65536 (2^16)	42.6 Ops/sec

Autogenerated LLM Summary (model gpt-4o-mini, generated one year ago):

LLMs can make mistakes. Check important info.

### Overview of the Benchmark

The benchmark is designed to evaluate the performance of the **radix sort** algorithm with various numeral bases, where radix sort is a non-comparative sorting algorithm that sorts numbers digit by digit. The benchmark involves running the `radixSort` function over an array of random integers generated up to a large number (10 trillion) using different bases ranging from binary (base 2) to hexadecimal and beyond.

### Benchmark Methodology

#### Comparison of Options

The benchmark tests radix sort using multiple bases:

1. **Base 2 (Binary)**
2. **Base 8 (Octal)**
3. **Base 10 (Decimal)**
4. **Base 16 (Hexadecimal)**
5. **Base 256 (2^8)**
6. **Base 512 (2^9)**
7. **Base 1024 (2^10)**
8. **Base 2048 (2^11)**
9. **Base 4096 (2^12)**
10. **Base 8192 (2^13)**
11. **Base 16384 (2^14)**
12. **Base 32768 (2^15)**
13. **Base 65536 (2^16)**

### Pros and Cons of Radix Sort

#### Pros

- **Time Complexity:** Radix sort can achieve O(nk) time complexity, where n is the number of elements and k is the number of digits in the maximum number (in input range) when implemented correctly. This can outperform comparison sorts (like quicksort or mergesort) in many situations, especially when the range of numbers is limited.
- **Non-comparative:** It sorts without needing to compare elements, which can lead to performance improvements in specific data scenarios.

#### Cons

- **Memory Usage:** Radix sort requires additional space for buckets, making its space complexity O(n + k), which can be significant for large datasets or large k (number of distinct digits).
- **Dependency on Digit Length:** The efficiency of radix sort is heavily influenced by the range and distribution of data. If the input numbers have long digits, the performance could decline.

### Considerations

- **Base Choice:** The choice of base can drastically affect performance. Lower bases (like 2) will generally lead to more iterations over the list since sorting is done digit by digit, thus potentially increasing execution time, while higher bases (like 65536) can reduce the number of iterations but may increase complexity in terms of digits.
- **Suitable Scenarios:** Radix sort is particularly efficient when sorting integers or strings of fixed lengths, as it leverages the structure of the data. For large integers with many different digits or lengths, other sorting algorithms might be more optimal.

### Other Libraries or Methods

In addition to radix sort, other sorting algorithms can be employed for comparison:

1. **QuickSort:** A divide-and-conquer algorithm, quicksort generally performs well on average (O(n log n)) but can degrade to O(n²) in the worst case without good pivot selection.
2. **MergeSort:** Stable and O(n log n) in worst-case scenarios, suitable for linked lists or when data should be sorted without disrupting original sequences.
3. **HeapSort:** Provides O(n log n) time complexity consistently and can be more memory efficient than merge sort.
4. **Timsort:** Used in Python as the default sorting algorithm, Timsort has a robust merging approach that benefits from runs of ordered data, achieving optimal performance on real-world data scenarios.

These alternatives may be used based on the data characteristics and performance requirements desired in specific applications.

Related benchmarks: