Algorithms

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. The largest element "bubbles" to the end of the list like an air bubble. Advantage: Extremely simple to understand and implement; detects already sorted lists very quickly. Disadvantage: Very inefficient for large lists (runtime O(n²)). Rarely used in practice. Wikipedia

Cocktail Sort (also Shaker Sort) is an extension of Bubble Sort. Instead of only moving from left to right, it reverses direction on each pass, alternately pushing the largest element to the right and the smallest to the left. Advantage: Faster than Bubble Sort, because small elements at the end move to the front more quickly (solving the "turtle problem"). Disadvantage: Stays in the O(n²) runtime class, so it remains inefficient for large data sets. Wikipedia

Quick Sort follows the "divide and conquer" principle. A "pivot" element is selected, and the array is divided into two halves: elements smaller than the pivot and elements larger than the pivot. Advantage: On average one of the fastest sorting algorithms (O(n log n)); requires no additional memory (in-place). Disadvantage: Slow in the worst case (O(n²)) if the pivot is chosen poorly. Is not stable (changes order of equal elements). Wikipedia

Heap Sort organizes the data initially into a special tree structure (Binary Heap). The largest element (the root) is extracted and sorted to the end, then the tree is repaired. Advantage: Guarantees a fast runtime of O(n log n), even in the worst case. Requires almost no additional memory. Disadvantage: Often slightly slower than Quick Sort in practice because the jumps in memory (heap structure) utilize the CPU cache less effectively. Wikipedia

Tim Sort is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It divides the array into small 'runs' and sorts each using Insertion Sort, then merges them step by step using Merge Sort. Advantage: Extremely efficient on real-world data that is often partially sorted — O(n log n) in the worst case and O(n) in the best case. It is the standard sorting algorithm in Python and Java. Disadvantage: More complex to implement than a pure algorithm and requires additional memory for the merge step. Wikipedia

Original work

• C. A. R. Hoare (1961): Algorithm 64: Quicksort
• J. W. J. Williams (1964): Algorithm 232: Heapsort
• Tim Peters (2002): listsort.txt (Timsort design notes)
• Folklore, no single inventor; the name "bubble sort" is by Kenneth E. Iverson (1962): Bubble sort and cocktail shaker sort

How it works

Each algorithm runs to the end first and stores a copy of the array (snapshot) in a list at every comparison and every swap. The animation then replays the snapshots at 100 ms per step. Execution time is the run including the copies, not the animation. Comparisons and writes count up during the animation.

• Bubble sort and cocktail sort: O(n²) comparisons, in place. Cocktail sort changes direction every pass and stops as soon as a pass swaps nothing.
• Quick sort: Lomuto partition with the last element as pivot, recursive. Average O(n log n), worst case O(n²), for example on already sorted data.
• Heap sort: builds a max heap inside the array (heapify from the middle to the front) and swaps the root to the end. Always O(n log n), no extra memory.
• Tim sort (simplified): insertion sort on fixed blocks of 32 elements, then bottom-up merge with helper arrays. No run detection and no galloping like the original. With 200 bars that is 7 blocks and 3 merge levels.
• Memory: the snapshot list is the biggest item, O(steps · n). Bubble sort with 200 bars produces up to about 40,000 snapshots of 200 entries each.

Source code:sorting.service.ts

Note The choice of the "best" sorting algorithm depends heavily on the data and the constraints. In computer science, three scenarios are often considered:

• Best Case: The data is already nearly sorted (Bubble Sort shines here, for example).
• Average Case: The statistical norm.
• Worst Case: The data is arranged in the most unfavorable way possible (Quick Sort performs poorly here without optimization, while Heap Sort remains stable).

Additionally, there is almost always a Time-Space Trade-off: Algorithms that are extremely fast (like Merge Sort) often require a lot of additional working memory. Algorithms that work directly in existing memory (like Heap Sort) save space but are sometimes more complex or slightly slower. Thus, there is no "one-size-fits-all" solution.