Sorting Algorithms Simulation

About this experiment

Watch bubble sort, insertion sort and merge sort transform the same input into ascending order. Pause at a comparison, step through each write, or move backward through the complete trace. Separate counts for value comparisons and main-array writes help distinguish algorithmic work from animation duration.

Learning goals

Trace comparisons and writes in three comparison sorting algorithms
Compare performance on shuffled, sorted and reversed inputs
Distinguish quadratic worst-case growth from n log n growth

How to use it

1Keep the shuffled input and array length fixed. Finish bubble sort and record its comparisons and writes.
2Restart with insertion sort, then merge sort, using the same input. Compare final counts.
3Try sorted input and inspect the early exit of bubble sort and the short insertion-sort comparisons.
4Use Previous and the trace slider to inspect a merge. Temporary buffers can hold values no longer visible at their original main-array positions.

The model

C_{bubble, worst} = \frac{n ( n - 1 )}{2}

Worst-case bubble-sort value comparisons

T_{insertion, worst} = O (n^{2}), T_{merge, worst} = O (n lo g n)

Worst-case time growth for insertion and merge sort

W_{swap} = 2

A swap is counted as two writes to the main array

Assumptions

Inputs contain unique integers from 1 to n. Shuffling uses a fixed seed so every algorithm receives identical data.
A comparison is a test between data values, not an index or loop-bound test. A write is an assignment to the main array, including an unchanged insertion key.
Merge-sort temporary-buffer copies are excluded from the write count. Extra memory use is not included in the displayed operation totals.
Playback speed is chosen for teaching and is not a wall-clock performance benchmark.

Try this in class

Q1Why does bubble sort need only n − 1 comparisons for already sorted input in this implementation?
Q2Which algorithm performs fewer comparisons on reversed input at the same array length?
Q3Why is the number of animation frames not a reliable measure of algorithm speed?

Frequently asked questions

Why do values briefly appear duplicated during insertion or merge sort?

A value can be held in a temporary key or merge buffer while the main array is overwritten. The visualization shows main-array contents at each write; uniqueness is restored when the operation completes.

Does merge sort always use fewer writes?

No. Merge sort has efficient comparison growth but writes merged results back repeatedly. Operation counts depend on the input and on exactly which assignments are counted.