Published by Dimitris Kougioumtzis · Updated
Distribute into ten buckets, sort each bucket by insertion, then concatenate.
Distribute values among ordered buckets, sort inside each bucket, then concatenate; distribution determines local work.
When to use Bucket sort
Numeric data with a predictable bounded distribution.
Choosing an alternative
Counting sort stores frequencies for individual keys.
Worked example: input and state changes
Example input
38, 12, 65, 8, 43, 27, 91, 19
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 38, 12, 65, 8, 43, 27, 91, 19 ], "active": [] }Step 4: Place 8 in bucket 0.
State at this checkpoint
{ "values": [ 38, 12, 65, 8, 43, 27, 91, 19 ], "active": [ 3 ] }Step 9: Collect sorted bucket 0.
State at this checkpoint
{ "values": [ 8, 12, 65, 8, 43, 27, 91, 19 ], "active": [ 0 ] }Step 13: Collect sorted bucket 3.
State at this checkpoint
{ "values": [ 8, 12, 19, 27, 38, 27, 91, 19 ], "active": [ 4 ] }Step 17: Complete: values are in ascending order.
State at this checkpoint
{ "values": [ 8, 12, 19, 27, 38, 43, 65, 91 ], "active": [] }
Expected final state
Complete: values are in ascending order.
Complexity and input bounds
Family: Sorting. Time complexity: O(n²) worst; O(n + k) expected.
Space complexity: O(n + k) storage for k buckets.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
2ā24 comma-separated integers between 0 and 99.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Expected linear performance assumes suitable distribution and bucket policy; clustering can produce quadratic work.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | // Sorts a in place. n is the array length. Return value 0 indicates completion. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n) { let count = Array(256).fill(0); let start = Array(256).fill(0); let temp = Array(256).fill(0); for (let i = 0; i < n; i++) { count[Math.floor(a[i] / 10)]++; } for (let b = 1; b < 10; b++) { start[b] = start[b - 1] + count[b - 1]; } for (let i = 0; i < n; i++) { let b = Math.floor(a[i] / 10); temp[start[b]++] = a[i]; } let left = 0; for (let b = 0; b < 10; b++) { let end = left + count[b]; for (let i = left + 1; i < end; i++) { let j = i; while (j > left && temp[j - 1] > temp[j]) { let t = temp[j]; temp[j] = temp[j - 1]; temp[j - 1] = t; j--; } } left = end; } for (let i = 0; i < n; i++) { a[i] = temp[i]; } return 0; } |
Source
No original paper has been verified for this entry. This source is a reference text or teaching reference, not an asserted original publication.
- The Art of Computer Programming, Volume 3: Sorting and Searching (2nd edition)
Donald E. Knuth (1998). Reference book.