Published by Dimitris Kougioumtzis · Updated
Recursively split the array, then merge sorted halves.
Merge neighboring sorted runs by repeatedly taking the smaller front value; the sorted-run invariant makes each decision local.
When to use Merge sort
Stable ordering and predictable large-input performance.
Choosing an alternative
Heapsort avoids a full merge buffer.
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 12: Choose next value from sorted halves.
State at this checkpoint
{ "values": [ 12, 38, 8, 65, 43, 27, 91, 19 ], "active": [ 1, 3 ] }Step 25: Choose next value from sorted halves.
State at this checkpoint
{ "values": [ 8, 12, 38, 65, 27, 43, 19, 91 ], "active": [ 4, 6 ] }Step 37: Choose next value from sorted halves.
State at this checkpoint
{ "values": [ 8, 12, 38, 65, 19, 27, 43, 91 ], "active": [ 2, 6 ] }Step 49: 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 log n).
Space complexity: O(n) merge buffer.
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 implementation needs an output buffer and is not a constant-space in-place sort.
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 temp = Array(256).fill(0); for (let width = 1; width < n; width *= 2) { for (let l = 0; l < n; l += 2 * width) { let mid = l + width; if (mid > n) { mid = n; } let r = l + 2 * width; if (r > n) { r = n; } let i = l; let j = mid; let k = l; while (i < mid || j < r) { if (j >= r || (i < mid && a[i] <= a[j])) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } for (k = l; k < r; k++) { a[k] = temp[k]; } } } 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.