Sorting Algorithm Visualizer — See How Sorting Algorithms Work

Algorithm Time and Space Complexity

How to Use the Sorting Visualizer

1. Open the sorting algorithm visualizer.
2. Choose an algorithm from the dropdown (Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quicksort, or Heapsort).
3. Set the array size — larger arrays make the performance differences between algorithms more visible.
4. Choose the initial order: random, nearly sorted, reverse sorted, or all equal. Different algorithms perform very differently on each.
5. Click Start. The visualizer animates each comparison and swap, colour-coding elements being compared, swapped, or already sorted.
6. Use the speed slider to slow down or speed up the animation. Slow speed shows individual steps; fast speed demonstrates overall performance.

When to Use Each Algorithm

Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each full pass through the array, the largest unsorted element "bubbles up" to its correct position at the end.

On an array of n elements, bubble sort makes at most n−1 passes, each with at most n−1 comparisons — giving O(n²) time in the worst case. An optimisation: if no swaps occurred in a pass, the array is already sorted and the algorithm can terminate early — giving O(n) for already-sorted input.

Despite being the most famous sorting algorithm in introductory courses, bubble sort is almost never used in production code. Its O(n²) average performance is dramatically worse than O(n log n) algorithms for large arrays.

Selection Sort

Selection sort divides the array into a sorted portion (left) and an unsorted portion (right). On each pass, it scans the unsorted portion to find the minimum element, then swaps it into position at the end of the sorted portion.

Selection sort always makes exactly O(n²) comparisons regardless of input order — unlike bubble sort, it doesn't benefit from nearly-sorted data. However, it makes at most O(n) swaps, which makes it useful when write operations are particularly expensive (e.g., writing to flash memory).

Insertion Sort

Insertion sort builds a sorted array one element at a time. For each new element, it is inserted into its correct position within the already-sorted portion by shifting larger elements right.

Insertion sort is remarkably efficient for:

• Small arrays (n < 20): low overhead and good cache performance
• Nearly-sorted arrays: O(n) performance when each element is only a few positions from its final position
• Online sorting: new elements can be inserted without reprocessing sorted elements

Python's standard sort (TimSort) uses insertion sort for runs shorter than 64 elements.

Merge Sort

Merge sort divides the array into halves recursively until each sub-array has one element (trivially sorted), then merges pairs of sorted sub-arrays together. The merge step takes O(n) time; with O(log n) levels of recursion, total time is O(n log n).

Key properties of merge sort:

• Guaranteed O(n log n): unlike quicksort, it never degrades to O(n²)
• Stable: elements with equal keys maintain their original relative order
• Parallelisable: the recursive divide-and-conquer structure maps naturally to parallel processing
• Requires O(n) extra space: for the temporary arrays during merging

Merge sort is the standard algorithm for sorting linked lists, where random access is expensive but sequential traversal and pointer manipulation are cheap.

Quicksort

Quicksort selects a pivot element and partitions the array into elements smaller than the pivot (left) and elements larger than the pivot (right). The algorithm is then applied recursively to each partition.

The choice of pivot is critical:

• First element: Simple but degrades to O(n²) on sorted input (a common real-world case)
• Random element: Avoids worst-case inputs for sorted/nearly-sorted data; O(n²) still possible but extremely unlikely
• Median-of-three: Takes the median of first, middle, and last elements as pivot; good practical performance

Quicksort is typically the fastest sorting algorithm in practice because of its excellent cache performance (it accesses elements sequentially during partitioning) despite its O(n²) worst case.

What Does "Stable" Mean?

A sorting algorithm is stable if it preserves the relative order of elements with equal keys. For example, if you sort a list of students by grade, a stable sort ensures that students with the same grade appear in the same order they appeared in the original list.

Stability matters when sorting by multiple criteria: if you first sort by first name (stable sort) and then sort by last name, a stable sort for the second step will keep first names in alphabetical order within each last name group. An unstable sort may scramble the first-name ordering.

Stable algorithms: bubble sort, insertion sort, merge sort, TimSort. Unstable: selection sort, quicksort, heapsort.

Big-O Notation and Complexity Classes

Time complexity describes how an algorithm's running time grows with input size n:

• O(n): Linear — time grows proportionally with n. Insertion sort on nearly-sorted input.
• O(n log n): Linearithmic — slightly worse than linear. Merge sort, quicksort (average), heapsort.
• O(n²): Quadratic — time grows with the square of n. Bubble sort, selection sort, insertion sort (worst case).

The practical difference between O(n log n) and O(n²) is dramatic for large n: for n = 1,000,000 elements, n log n ≈ 20,000,000 operations vs. n² = 1,000,000,000,000 operations — a 50,000× difference.

Common Questions

Why is quicksort called "quick" if its worst case is O(n²)?

Despite the O(n²) worst case, quicksort consistently outperforms merge sort and heapsort in practice on random data because of cache efficiency and low constant factors. The "average" case of O(n log n) occurs on essentially all random inputs. With a randomised pivot, the probability of hitting the O(n²) case is astronomically small. The name refers to its empirical speed, not theoretical worst-case guarantees.

What sorting algorithm does Python use?

Python uses TimSort, invented by Tim Peters in 2002 specifically for Python. It is a hybrid of merge sort (for large runs) and insertion sort (for small runs). TimSort identifies naturally occurring sorted subsequences ("runs") in the data and merges them efficiently. It achieves O(n) on real-world data that is nearly sorted, which is extremely common in practice. Java 7+ uses a similar algorithm (dual-pivot quicksort for primitives, TimSort for objects).

Can sorting be done faster than O(n log n)?

For comparison-based sorting (where elements are compared to determine their order), O(n log n) is provably optimal — no comparison sort can do better in the worst case. However, non-comparison sorts can be faster: counting sort and radix sort are O(n) but only work for specific input types (integers within a limited range). For n = 10 billion integers, radix sort would dramatically outperform merge sort.