SortVivo - Sort Algorithm Visualization

SymMerge sort(2004)

O(n log² n) ✓ Stable ✓ In-place ✓ Adaptive

Combined with: Insertion sort (small ranges)

🔧 How it works

Bottom-up in-place stable sort that replaces Rotate merge sort's repeated small rotations with SymMerge: one symmetric binary search finds the optimal split point, one rotation bridges the two runs, and two recursive calls finish each half.

🎯 Key property

The symmetric binary search costs only O(log n) comparisons per recursive call, and by the recurrence T(n) = 2T(n/2) + O(log n) each merge requires only O(n) total comparisons, reducing the overall sort from O(n log² n) to O(n log n) comparisons, while element moves remain O(n log² n).

👁 Watch for

Compare the binary search tests s[p−c] ≥ s[c] at the symmetric mirror position; the split found is optimal, so exactly one rotation and no redundant scans are needed
Swap a single rotation, implemented via 3-reversal, moves all misplaced elements into position at once, rather than the many small rotations that Rotate merge sort performs
End of merge two recursive SymMerge calls handle the two resulting subproblems on each half of the range, halving the problem at each level until the base case is reached

🕰 History 🌳 Lineage ⚡ Optimization

Initial State

This is the array before sorting. Follow SymMerge sort step by step.

Recursion Tree

0 / 946 ops ( 0.0%) 0.0%