Published by Dimitris Kougioumtzis · Updated
Partition around a pivot, then recursively sort both partitions.
Partition around a pivot and sort the two resulting intervals independently; partitioning alone does not order either side.
When to use Quicksort
Exploring divide-and-conquer and pivot choice.
Choosing an alternative
Merge sort guarantees logarithmic levels; quickselect needs only one partition branch.
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 7: Partition around pivot 19.
State at this checkpoint
{ "values": [ 12, 8, 65, 38, 43, 27, 91, 19 ], "active": [ 4, 7 ] }Step 13: Partition around pivot 65.
State at this checkpoint
{ "values": [ 8, 12, 19, 38, 43, 27, 91, 65 ], "active": [ 3, 7 ] }Step 20: Place pivot.
State at this checkpoint
{ "values": [ 8, 12, 19, 38, 43, 27, 65, 91 ], "active": [ 6 ] }Step 26: 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 log n) average.
Space complexity: O(n) worst-case pending intervals.
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
This endpoint-pivot reference can take quadratic time on sorted or adversarial input.
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 | // 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 stack = Array(256).fill(0); let top = 0; stack[top++] = 0; stack[top++] = n - 1; while (top > 0) { let r = stack[--top]; let l = stack[--top]; if (l >= r) { continue; } let pivot = a[r]; let i = l; for (let j = l; j < r; j++) { if (a[j] < pivot) { let t = a[i]; a[i] = a[j]; a[j] = t; i++; } } let pivotTemp = a[i]; a[i] = a[r]; a[r] = pivotTemp; stack[top++] = l; stack[top++] = i - 1; stack[top++] = i + 1; stack[top++] = r; } return 0; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- Quicksort
C. A. R. Hoare (1962). Research paper.