In sorting with evolving data [AKMU11], the input data is changing as the sorting algorithm is executing. More specifically, every sorting step is followed by b mixing steps. The sorting algorithm maintains an ordering ν and the goal is to keep it as close to the true ordering ρ (which evolves over time).
The color of an element shows how close it is to the correct place (the greener the closer). The maximum of these is the maximum deviation (mdev) and the total is the total deviation (tdev). Naive sort [M14] which picks a random pair of adjacent elements and sorts them if they are out of order, achieves asymptotically optimal mdev and tdev.
.
Instructions
Basic usage: (1) Select an algorithm, mixing step type and a value for b. (2) Click reset and (3) Click "next step" or "play".
See quick convergence: Click "shuffle" to enter a random permutation. Set "duration" to 50ms and click "play".
See plots: Check "Plot tdev/mdev" and click play