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

Go 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)

Historical Performance Data aggregated from 9 community runs

Desktop Results:

Chrome 9 runs

base 1024 (2^10)

197/s

base 4096 (2^12)

192/s

base 256 (2^8)

186/s

base 16

89/s

base 16384 (2^14)

79/s

base 10

72/s

base 8

62/s

base 65536 (2^16)

49/s

base 2

19/s

Fastest: base 1024 (2^10) (10.1x faster)

View exact numbers

✓ base 1024 (2^10): 197 ops/sec
• base 4096 (2^12): 192 ops/sec
• base 256 (2^8): 186 ops/sec
• base 16: 89 ops/sec
• base 16384 (2^14): 79 ops/sec
• base 10: 72 ops/sec
• base 8: 62 ops/sec
• base 65536 (2^16): 49 ops/sec
• base 2: 19 ops/sec

Results show median performance across all community submissions. Run this benchmark yourself to verify on your device.

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

base 2048 (2^11)

272/s

base 512 (2^9)

232/s

base 4096 (2^12)

221/s

base 1024 (2^10)

221/s

base 256 (2^8)

186/s

base 8192 (2^13)

160/s

base 16384 (2^14)

107/s

base 16

88/s

base 32768 (2^15)

87/s

base 10

71/s

base 8

61/s

base 65536 (2^16)

43/s

base 2

19/s

View exact numbers

Test name	Executions per second
✓ base 2048 (2^11)	272 Ops/sec
base 512 (2^9)	232 Ops/sec
base 4096 (2^12)	221 Ops/sec
base 1024 (2^10)	221 Ops/sec
base 256 (2^8)	186 Ops/sec
base 8192 (2^13)	160 Ops/sec
base 16384 (2^14)	107 Ops/sec
base 16	88 Ops/sec
base 32768 (2^15)	87 Ops/sec
base 10	71 Ops/sec
base 8	61 Ops/sec
base 65536 (2^16)	43 Ops/sec
base 2	19 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.

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

Go to the latest 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)

Historical Performance Data aggregated from 9 community runs

Desktop Results:

Chrome 9 runs

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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

Related benchmarks

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)`