Complete Documentation

Overview

Welcome to VisualSorting—a comprehensive, interactive educational tool designed to help you understand how different sorting algorithms work at a fundamental level. This application provides real-time visual feedback as arrays are sorted, with color-coded highlighting that distinguishes between different operations.

Visual Feedback System

The visualizer uses a consistent color coding system throughout all modes:

Educational Philosophy

This visualizer goes beyond simple demonstrations. By watching algorithms work step-by-step, you develop intuition about:

• Why some algorithms are faster: See how divide-and-conquer approaches tackle large problems efficiently
• Trade-offs between algorithms: Observe how some use more comparisons but fewer swaps, or vice versa
• Best and worst cases: Experiment with different data distributions to see when algorithms excel or struggle
• Memory usage patterns: Understand why some algorithms need extra space while others work in-place

Quick Start Guide

Get sorting in under 30 seconds with this step-by-step guide:

Adjusting Array Size

The size slider controls how many elements are in your array (default range: 10-400 elements). Consider these guidelines:

• Small arrays (10-30): Best for learning. You can follow individual elements and understand each step.
• Medium arrays (50-100): Good for comparing algorithm patterns. You'll see characteristic shapes emerge.
• Large arrays (200-400): Best for appreciating efficiency differences. Slow algorithms become visibly slower.

Understanding Speed Settings

The speed slider controls the delay between visualization steps:

• Slow (left): ~500ms between steps. Perfect for step-by-step analysis and teaching.
• Medium (center): ~50ms between steps. Balanced view of algorithm behavior.
• Fast (right): ~1ms between steps. Shows overall patterns quickly. May appear instant for efficient algorithms.

Interface Tour

Familiarize yourself with all the components of the VisualSorting interface:

Navigation Tabs

The top navigation bar provides access to six distinct modes:

Statistics Panel

The floating statistics panel (top-left during visualization) shows:

• Comparisons (Comp): How many times two elements have been compared. This is the primary metric for comparison-based sorts.
• Swaps: How many times elements have been moved or exchanged. Important for understanding memory write operations.

Advanced Options Panel

Click "Advanced Options" to expand additional settings (covered in detail in the Features section).

All Features

Explore the full range of features available in the Advanced Options panel and throughout the application:

Array Distribution Types

Control how the initial array is generated to test algorithms under different conditions:

Audio Features

Enable sound effects for an auditory dimension to your sorting experience:

• Pitch Mapping: Each element's value is mapped to a musical pitch. Higher values produce higher tones, lower values produce lower tones.
• Comparison Sounds: Short tones play when elements are compared, creating a melodic pattern unique to each algorithm.
• Completion Sound: A satisfying ascending scale plays when sorting completes.

Visual Options

• Show Bar Values: Display the numeric value on each bar. Helpful for small arrays when you want to track specific numbers.
• Rainbow Mode: Color bars based on their value (HSL color mapping). Creates beautiful visual patterns, especially during Radix and Bucket sorts.
• 3D Mode: Add depth perspective to the bar visualization. Purely aesthetic but provides a fresh visual experience.
• Colorblind Modes: Protanopia and Tritanopia-friendly color schemes ensure accessibility for users with color vision deficiencies.

Save/Load System

Preserve your arrays for consistent testing:

• Save Array: Store the current array state to browser localStorage. Persists between sessions.
• Load Array: Restore a previously saved array. Great for comparing how different algorithms handle identical data.

Keyboard Shortcuts

Power users can control the visualizer entirely from the keyboard:

Custom Arrays

Load your own data for sorting visualization instead of using randomly generated arrays. This feature is available in three modes with different size limits optimized for each use case.

Visualizer Mode (Max 500 Elements)

In the main Visualizer tab, expand "Advanced Options" to find the Custom Array section:

• Text Input: Enter comma-separated numbers directly (e.g., 5, 3, 8, 1, 9, 2)
• File Upload: Click "Upload File" to load from JSON, TXT, or CSV files
• Automatic Normalization: Values are automatically scaled to 1-100% for proper visualization

Compare Mode (Max 500 Elements)

Race algorithms on your own data instead of random arrays:

• Click the "📁 Load Array" button in the race controls
• All racers will use identical copies of your custom array
• Click the "✕" button to clear and return to random arrays

Benchmark Mode (Max 100,000 Elements)

For serious performance testing with real-world data:

• Select "Custom Array" from the Distribution dropdown
• Upload a file with up to 100,000 elements
• Benchmarks run at full speed without visualization delays

Supported File Formats

Benchmarking

The Benchmark tab provides objective performance measurements by running algorithms at full speed in a Web Worker (background thread). This ensures accurate timing without UI rendering overhead.

How Benchmarking Works

1. Array Generation: For each test run, a fresh array is generated according to your selected distribution (or your custom array is used)
2. Identical Copies: Each algorithm receives an identical copy of this array, ensuring fair comparison
3. Full-Speed Execution: Algorithms run without any visualization delays—measuring actual computational performance
4. Statistics Collection: Time (milliseconds), comparisons, and swaps are tracked precisely
5. Multiple Runs: If you specify multiple test runs, results are averaged for statistical significance

Configuration Options

Understanding the Score

Each algorithm receives a composite score from 0-100 based on weighted performance metrics:

Exporting Results

After benchmarking, export your results for further analysis:

• CSV Export: Spreadsheet-compatible format for Excel, Google Sheets, or data analysis tools
• JSON Export: Structured data format for programmatic analysis or archival
• Export Average vs All: Choose to export averaged results or individual run data

Algorithm Race

The Compare tab lets you pit algorithms against each other in a visual race. All competitors sort identical copies of the same array simultaneously, so you can directly observe which approaches are faster.

Setting Up a Race

1. Add Racers: Click "+ Add Racer" to add algorithm panels (up to 25 maximum)
2. Choose Algorithms: Each panel has a dropdown—select different algorithms to compare
3. Configure Array: Use the size slider (10-100 elements) or load a custom array
4. Adjust Speed: The speed slider controls all racers simultaneously
5. Start Race: Click "Start Race" and watch them compete!

Race Features

• Live Statistics: Each panel shows real-time comparison and swap counts
• Finish Detection: Panels turn green when their algorithm completes
• Ranking: Gold, silver, and bronze badges appear for the top 3 finishers
• Leaderboard: Full race results with timing appear in a table after the race
• Pause/Resume: Pause the race at any point to analyze current state

Race Strategies

Try these interesting matchups:

• Simple vs Efficient: Bubble Sort vs Quick Sort on 50+ elements—see the dramatic difference
• Variants Battle: Quick Sort vs Dual-Pivot Quick Sort vs IntroSort
• Edge Cases: Compare on "Reversed" arrays to expose worst-case behavior
• Stable Showdown: Merge Sort vs Tim Sort vs Insertion Sort on nearly-sorted data

Custom Algorithms

The Custom tab is a sandbox environment where you can write and visualize your own sorting algorithms using JavaScript. Your code runs in a secure iframe with access to helper functions that control the visualization.

Available API

Example Implementations

const n = arr.length;
for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
        await compare(j, j + 1);
        if (arr[j] > arr[j + 1]) {
            await swap(j, j + 1);
        }
    }
}

const n = arr.length;
for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - i - 1; j++) {
        await compare(j, j + 1);
        if (arr[j] > arr[j + 1]) {
            await swap(j, j + 1);
            swapped = true;
        }
    }
    // If no swaps occurred, array is sorted
    if (!swapped) break;
}

const n = arr.length;
for (let i = 1; i < n; i++) {
    let j = i;
    while (j > 0) {
        await compare(j - 1, j);
        if (arr[j - 1] > arr[j]) {
            await swap(j - 1, j);
            j--;
        } else {
            break;
        }
    }
}

Best Practices

• Always use await: The compare(), swap(), and sleep() functions are async. Forgetting await will cause visualization to fail.
• Stay in bounds: Array indices must be 0 to arr.length-1. Out-of-bounds access will cause errors.
• Don't modify arr directly: Always use swap() to exchange elements so the visualizer updates correctly.
• Test with small arrays: Start with 10-20 elements to debug your algorithm before scaling up.

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms to understand and implement. It works by repeatedly "bubbling" larger elements toward the end of the array through adjacent comparisons and swaps. The name comes from the way smaller elements gradually rise to the top of the list, like bubbles rising in water.

Detailed Algorithm

1. Outer Loop (passes): Iterate through the array n-1 times, where n is the array length. Each pass guarantees one more element is in its final position.
2. Inner Loop (comparisons): For each pass, compare adjacent elements from the beginning up to the unsorted portion.
3. Comparison: If the left element is greater than the right element, they are in the wrong order.
4. Swap: Exchange the positions of the two elements to put them in correct relative order.
5. Optimization: After each pass, the largest unsorted element is now at the end of the unsorted portion. We can skip it in subsequent passes.
6. Early Termination: If an entire pass completes with no swaps, the array is already sorted. We can exit early.

Complexity Analysis

Visual Pattern

In the visualizer, you'll notice a distinctive pattern: after each pass, the rightmost unsorted element turns green as it reaches its final position. The sorted portion grows from right to left, creating a "wave" effect. Small elements "bubble up" through multiple passes—each pass moves them one position closer to their destination.

The "Turtle" Problem

Bubble Sort has an asymmetric behavior: large elements at the beginning ("rabbits") quickly move to the end in one pass, but small elements at the end ("turtles") can only move one position per pass. This is why Cocktail Shaker Sort was invented—it bubbles in both directions to handle turtles more efficiently.

Selection Sort

Selection Sort works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning of the sorted portion. Unlike Bubble Sort, it minimizes the number of swaps—making exactly n-1 swaps regardless of input. This makes it theoretically optimal for situations where writes are expensive.

Detailed Algorithm

1. Initialize: Consider position 0 as the start of the unsorted region
2. Find Minimum: Scan the entire unsorted region to find the smallest element
3. Swap: Exchange the minimum with the first unsorted element
4. Advance: Move the boundary between sorted and unsorted regions one position right
5. Repeat: Continue until all elements are in the sorted region

Complexity Analysis

Visual Pattern

In the visualizer, you'll see a clear division between sorted (green, left) and unsorted (blue, right) portions. During each pass, watch as the algorithm scans through all unsorted elements (yellow highlights moving right) to find the minimum. Then a single swap places the minimum in position. The sorted region grows steadily from left to right.

Key Insight: Comparison vs Swap Trade-off

Selection Sort always performs exactly n(n-1)/2 comparisons—it cannot detect if the array is already sorted. However, it makes at most n-1 swaps (one per position). This makes it valuable for:

• Flash memory: Where write cycles are limited and expensive
• Large records: Where swapping is costly but comparison is cheap
• Visualization: The simple, predictable pattern is educational

Double Selection Sort

Double Selection Sort (also called Bidirectional Selection Sort or Cocktail Selection Sort) improves upon Selection Sort by finding both the minimum AND maximum in each pass. This effectively halves the number of passes needed, though the total comparisons remain O(n²).

Detailed Algorithm

1. Initialize: Set left boundary at 0, right boundary at n-1
2. Find Both Extremes: In a single scan, track both minimum and maximum values
3. Place Minimum: Swap minimum to the left boundary position
4. Place Maximum: Swap maximum to the right boundary position (handling the case where max was at left boundary)
5. Shrink: Move left boundary right, right boundary left
6. Repeat: Continue until boundaries meet

Complexity Analysis

Visual Pattern

Watch as sorted regions grow from BOTH ends simultaneously. The left side accumulates minimums (green from left) while the right side accumulates maximums (green from right). The unsorted middle section shrinks from both sides, creating a satisfying "closing" effect.

Insertion Sort

Insertion Sort builds the sorted array one element at a time by inserting each new element into its correct position among the already-sorted elements. It's exactly how most people sort playing cards in their hand—pick up a card and slide it into the right spot.

Detailed Algorithm

1. Start: Consider the first element as a sorted subarray of size 1
2. Take Next: Pick the first element from the unsorted portion
3. Compare Backwards: Compare it with elements in the sorted portion, moving right to left
4. Shift: Shift larger elements one position right to make room
5. Insert: Place the element in its correct position
6. Repeat: Continue until all elements are processed

Complexity Analysis

Visual Pattern

Watch as the sorted region (left, green) grows one element at a time. When a new element is picked, you'll see it compared against sorted elements moving leftward (yellow highlights). Elements shift right to make room, and the new element "slides" into its correct position.

Why Insertion Sort is Actually Useful

Despite O(n²) worst case, Insertion Sort has important practical applications:

• Small arrays: For n ≤ 15-20, Insertion Sort often beats O(n log n) algorithms due to lower overhead
• Nearly sorted data: Achieves near-O(n) performance when data is almost sorted
• Online algorithm: Can sort data as it arrives, one element at a time
• Hybrid algorithms: Used as the final step in Tim Sort, IntroSort, and others

Merge Sort

Merge Sort is the quintessential divide-and-conquer algorithm. It divides the array into halves, recursively sorts each half, then merges them back together. Its guaranteed O(n log n) performance makes it a reliable choice when consistent speed matters.

Detailed Algorithm

1. Base Case: If the array has 0 or 1 elements, it's already sorted—return immediately
2. Divide: Find the middle point and split the array into two halves
3. Conquer: Recursively sort the left half, then the right half
4. Merge: Combine the two sorted halves by comparing their elements one by one
5. Copy Back: Place the merged result back into the original array

The Merge Process (Key Step)

The merge operation is where the real work happens:

1. Create temporary arrays for left and right halves
2. Compare elements from both halves, always taking the smaller one
3. Place the smaller element in the result array
4. Continue until one half is exhausted
5. Copy remaining elements from the non-empty half

Complexity Analysis

Visual Pattern

In the visualizer, watch the recursive pattern unfold: the array is repeatedly split in half (no visible changes) until reaching single elements. Then the "merge" waves propagate upward—small sorted segments combine into larger ones. You'll see organized "fronts" of sorted elements meeting and merging.

3-Way Merge Sort

3-Way Merge Sort divides the array into THREE parts instead of two, then recursively sorts and merges them. While asymptotically equivalent to 2-way merge sort, it can be faster in practice due to fewer recursive calls and better cache behavior.

Detailed Algorithm

1. Divide: Split the array into three roughly equal parts
2. Conquer: Recursively sort each of the three parts
3. Merge: Combine all three sorted parts simultaneously

Why 3-Way?

The depth of recursion is log₃(n) instead of log₂(n), meaning fewer function calls. However, each merge step is more complex (comparing 3 elements instead of 2). The trade-off often favors 3-way for large arrays due to:

• Fewer recursive calls: log₃(n) ≈ 0.63 × log₂(n)
• Better cache utilization: Larger chunks stay in cache
• Reduced function call overhead: Significant for interpreted languages

Visual Pattern

Similar to standard Merge Sort, but the array splits into thirds. Watch as three "fronts" of sorted elements converge during each merge phase, creating a more distributed merge pattern.

Quick Sort

Quick Sort is often the fastest sorting algorithm in practice. It works by selecting a "pivot" element and partitioning the array around it—all elements smaller than the pivot go to the left, all larger go to the right. Then it recursively sorts the partitions.

Detailed Algorithm

1. Choose Pivot: Select an element as the pivot (our implementation uses the last element)
2. Partition: Rearrange so elements < pivot are left, elements> pivot are right
3. Place Pivot: Put pivot in its final sorted position between the partitions
4. Recurse: Apply Quick Sort to left partition, then right partition

The Partition Process

Partitioning is the heart of Quick Sort (Lomuto scheme):

1. Initialize a "wall" at the start of the array
2. Scan through elements: if element < pivot, swap it with the wall position and advance the wall
3. After scanning, swap the pivot into the wall position
4. Now everything left of wall < pivot, everything right> pivot

Complexity Analysis

Visual Pattern

Watch the dramatic partitioning process: elements "sweep" to either side of the pivot, which then locks into its final position (green). The distinctive pattern shows elements clustering around the pivot before the recursive calls process each side independently.

Dual-Pivot Quick Sort

Dual-Pivot Quick Sort (Yaroslavskiy's algorithm) uses two pivots to partition the array into three regions. Introduced in 2009, it became Java's default Arrays.sort() for primitive types in JDK 7, as it outperforms single-pivot Quick Sort by about 10% on average.

Detailed Algorithm

1. Choose Two Pivots: Select P1 and P2 where P1 ≤ P2 (typically first and last elements)
2. Three-Way Partition:
   • Left region: elements < P1
   • Middle region: elements between P1 and P2 (inclusive)
   • Right region: elements > P2
3. Place Pivots: Move P1 and P2 to their final positions
4. Recurse: Apply to all three partitions

Why Two Pivots Are Better

Mathematical analysis shows that dual-pivot requires fewer comparisons on average:

• Classic Quick Sort: ~2n ln(n) ≈ 1.39n log₂(n) comparisons
• Dual-Pivot: ~1.9n ln(n) ≈ 1.32n log₂(n) comparisons

The improved cache behavior and fewer recursive calls also contribute to real-world speedups.

Visual Pattern

Watch as two pivots (often at the edges initially) create THREE regions during partitioning. Elements cluster into small/medium/large groups before the pivots lock into place. The three-way recursion creates a more varied pattern than single-pivot Quick Sort.

IntroSort

IntroSort (Introspective Sort) is a hybrid algorithm that combines Quick Sort's speed with Heap Sort's guaranteed worst-case performance. When Quick Sort's recursion depth exceeds 2×log₂(n), it switches to Heap Sort to prevent O(n²) behavior. It's the default in C++ STL's std::sort.

Detailed Algorithm

1. Set Depth Limit: Calculate 2 × floor(log₂(n))
2. Quick Sort Phase: Begin with Quick Sort partitioning
3. Depth Check: If recursion depth exceeds limit, switch to Heap Sort
4. Small Array Optimization: For subarrays ≤ 16 elements, use Insertion Sort

Why This Works

IntroSort gets the best of three algorithms:

• Quick Sort: Fast average case with good cache behavior
• Heap Sort: Guaranteed O(n log n) worst case
• Insertion Sort: Low overhead for small arrays

Visual Pattern

On random data, you'll see typical Quick Sort behavior. On pathological inputs (sorted, reversed), watch as the algorithm detects deep recursion and smoothly transitions to Heap Sort's heapify-extract pattern. For small subarrays, Insertion Sort's sliding behavior appears.

Heap Sort

Heap Sort combines the advantages of guaranteed O(n log n) time with in-place sorting (O(1) extra space). It works by building a max-heap from the array, then repeatedly extracting the maximum element. The heap structure ensures efficient extraction.

Understanding the Heap

A max-heap is a complete binary tree where each parent is greater than its children. In an array representation:

• Parent of index i is at index floor((i-1)/2)
• Left child of index i is at index 2i + 1
• Right child of index i is at index 2i + 2

Detailed Algorithm

1. Build Max-Heap: Transform the array into a max-heap (O(n) time using bottom-up heapify)
2. Extract Maximum: Swap the root (maximum) with the last element
3. Reduce Heap Size: The last element is now in its final position
4. Restore Heap: Heapify the root to restore the max-heap property
5. Repeat: Continue until heap size is 1

Complexity Analysis

Visual Pattern

The visualization shows a fascinating two-phase process. During heap building, you'll see elements "bubbling up" and "sinking down" as the heap property is established. During extraction, watch as the maximum repeatedly goes to the end (turns green), and a new maximum rises to the root.

Shell Sort

Shell Sort is an optimization of Insertion Sort that allows swapping elements far apart. Instead of comparing adjacent elements, it compares elements separated by a "gap" that progressively shrinks. When the gap reaches 1, it becomes standard Insertion Sort on a nearly-sorted array.

Detailed Algorithm

1. Choose Gap Sequence: Start with a large gap (typically n/2) and shrink by half each pass
2. Gap-Insertion Sort: For each gap value, perform Insertion Sort on elements that are gap-positions apart
3. Reduce Gap: Divide gap by 2 (or use a different sequence)
4. Final Pass: When gap = 1, perform standard Insertion Sort

Gap Sequences Matter

The choice of gap sequence affects performance significantly:

Visual Pattern

Watch as the large initial gap causes distant element comparisons—elements "leap" across the array. As the gap shrinks, the pattern becomes more localized. By the final gap-1 pass, the array is nearly sorted, so Insertion Sort runs quickly.

Tim Sort

Tim Sort is a sophisticated hybrid algorithm designed for real-world data. Created by Tim Peters for Python in 2002, it's now the default sort in Python, Java (for objects), Android, and Swift. It exploits existing ordered sequences ("natural runs") for exceptional performance on partially sorted data.

Key Concepts

• Runs: Consecutive strictly increasing or decreasing sequences in the input
• minrun: Minimum run length (32-64), smaller runs are extended with Insertion Sort
• Run Stack: Runs are pushed onto a stack and merged according to invariants

Detailed Algorithm

1. Find Runs: Identify natural ascending/descending sequences in the input
2. Extend Short Runs: Use Insertion Sort to extend runs shorter than minrun
3. Merge Strategy: Push runs onto a stack, merge when size invariants are violated
4. Galloping: During merge, if one side consistently "wins," gallop through it in O(log n)
5. Final Merge: Continue until only one sorted run remains

Why Tim Sort Dominates Real Data

Real-world data often has natural order:

• Log files: Mostly sorted by timestamp
• Database results: Often already partially ordered
• User data: Alphabetical names, sequential IDs

Tim Sort achieves O(n) on already-sorted data and near-O(n) on partially-sorted data, while maintaining O(n log n) worst case.

Visual Pattern

Watch as the algorithm first scans for natural runs (you may see brief pauses during detection). Then observe Merge Sort-like behavior as runs are combined, but notice the adaptive galloping—sometimes merging accelerates dramatically when one side has many consecutive "winners."

Radix Sort (LSD)

Radix Sort (LSD - Least Significant Digit) is a non-comparison sorting algorithm that processes digits from right to left. It achieves linear time by circumventing the O(n log n) lower bound that applies to comparison-based sorts.

Detailed Algorithm

1. Find Maximum: Determine the maximum value to know how many digit passes are needed
2. Process Each Digit: Starting from the ones place (least significant)
3. Count Sort: Use Counting Sort as a stable subroutine to sort by current digit
4. Move Left: Advance to the next digit position (tens, hundreds, etc.)
5. Repeat: Continue until all digit positions are processed

Complexity Analysis

Visual Pattern

The visualization shows a chaotic-to-ordered progression. Watch as elements group by their last digit first, then by tens, then hundreds. Unlike comparison sorts, the final order only emerges at the very end—you'll see dramatic reorganization that suddenly snaps into sorted order.

Radix Sort (MSD)

MSD (Most Significant Digit) Radix Sort processes digits from left to right, recursively sorting buckets. Unlike LSD which shows chaos until the end, MSD shows sorted order emerging progressively from the largest values down.

Key Difference from LSD

• LSD: Sorts right-to-left, uses stable sort, all elements processed each pass
• MSD: Sorts left-to-right, recursive, can terminate early for buckets

Detailed Algorithm

1. Bucket by MSD: Group elements by their most significant (leftmost) digit
2. Recurse: Recursively sort each bucket by the next digit
3. Early Termination: Stop when bucket has 1 element or when last digit is reached
4. Concatenate: Buckets are already in order, just concatenate them

Visual Pattern

Watch as the array progressively organizes from high values to low. Elements with the largest MSD settle into position first, creating a "top-down" sorted appearance. This is more intuitive visually than LSD's "chaos until the end" approach.

Bucket Sort

Bucket Sort distributes elements into "buckets" based on their value ranges, sorts each bucket individually, then concatenates the results. It achieves O(n) time when data is uniformly distributed across buckets.

Detailed Algorithm

1. Create Buckets: Allocate empty buckets covering the value range
2. Scatter: Place each element in its corresponding bucket based on value
3. Sort Buckets: Sort each bucket (typically with Insertion Sort)
4. Gather: Concatenate all buckets in order to form the sorted array

Bucket Assignment

For values in range [0, max], bucket index = floor(value × numBuckets / (max + 1)). This ensures uniform distribution for uniformly random data.

Complexity Analysis

Visual Pattern

The visualization shows a beautiful scatter-gather effect. Watch as elements are distributed to buckets (colored by bucket), creating a rainbow pattern. Then each bucket sorts internally, and finally all buckets merge into the sorted result.

Counting Sort

Counting Sort achieves linear time by counting occurrences of each distinct value, then using arithmetic to determine final positions. It's the fastest possible sort when the value range k is small relative to n.

Detailed Algorithm

1. Find Range: Determine min and max values in the array
2. Create Count Array: Array of size (max - min + 1), initialized to zeros
3. Count: Increment count[value - min] for each element
4. Cumulate (for stability): Transform counts to cumulative sums for position calculation
5. Build Output: Place each element at its calculated position

Complexity Analysis

Visual Pattern

Watch as the algorithm first scans through the array counting values. Then, in consecutive positions, place elements based on their calculated indices. The sorted array emerges rapidly as elements snap into their final positions from left to right.

Gravity (Bead) Sort

Gravity Sort (Bead Sort) simulates physical beads falling on vertical poles. Imagine an abacus turned on its side—beads fall due to gravity, naturally arranging by count. It's theoretically O(n) with hardware implementation!

Detailed Algorithm

1. Setup: Create a grid with 'max' columns and 'n' rows
2. Place Beads: For each value v, place v beads in that row
3. Drop: Let beads "fall" due to gravity (column by column)
4. Count: The number of beads in each row after falling is the sorted value

Physical Analogy

Imagine vertical poles with n rows. Each number is represented by beads on that row. When gravity is applied, beads fall as far as they can. Rows with more beads (larger values) stack at the bottom, naturally sorting the array.

Visual Pattern

Watch as horizontal bars (representing beads) "fall" downward, stacking at the bottom. The largest values (most beads) accumulate first, creating a visually satisfying gravitational effect. It's one of the most intuitive sorting visualizations.

Comb Sort

Comb Sort improves on Bubble Sort by comparing elements separated by a shrinking gap. The gap shrinks by a factor of 1.3 each pass (empirically determined), quickly eliminating "turtles" (small values at the end).

Detailed Algorithm

1. Initialize Gap: Set gap = n / 1.3
2. Compare and Swap: Compare elements gap positions apart, swap if out of order
3. Shrink Gap: gap = gap / 1.3 (round down)
4. Final Pass: When gap = 1, perform Bubble Sort until no swaps occur

Why 1.3?

The shrink factor of approximately 1.3 (more precisely 1/(1-e^(-φ)) ≈ 1.247) was found empirically to give the best average performance. This eliminates most out-of-order pairs before the final gap-1 pass.

Cocktail Shaker Sort

Cocktail Shaker Sort (Bidirectional Bubble Sort) alternates between forward and backward passes, addressing Bubble Sort's "turtle" problem where small values at the end move slowly leftward.

Detailed Algorithm

1. Forward Pass: Bubble largest unsorted element to the right
2. Backward Pass: Bubble smallest unsorted element to the left
3. Shrink Bounds: Both left and right bounds move inward
4. Repeat: Continue until bounds cross (no unsorted elements remain)

Visual Pattern

Watch the "shaker" effect as the algorithm alternates direction. The sorted region grows from BOTH ends simultaneously, unlike Bubble Sort's single-direction growth. Large values go right, then small values go left, then repeat.

Gnome Sort

Gnome Sort (Stupid Sort) is conceptually the simplest sorting algorithm. A garden gnome sorts flower pots by comparing adjacent pots, swapping if needed, and stepping backward; otherwise stepping forward.

The Gnome Story

Imagine a garden gnome sorting a line of flower pots: "Look at the pot next to me and the one before. If they're in the wrong order, swap and step back. If they're right (or I'm at the start), step forward. Stop when I reach the end."

Detailed Algorithm

1. Start: Position at index 0
2. At Start?: If at position 0, move forward
3. In Order?: If current ≥ previous, move forward
4. Out of Order?: Swap current and previous, move backward
5. Repeat: Continue until position reaches n

Odd-Even Sort

Odd-Even Sort (Brick Sort) alternates between comparing odd-indexed pairs (1-2, 3-4, 5-6...) and even-indexed pairs (0-1, 2-3, 4-5...). It's designed for parallel processing where all pairs can be compared simultaneously.

Detailed Algorithm

1. Odd Phase: Compare/swap pairs (1,2), (3,4), (5,6)... in parallel
2. Even Phase: Compare/swap pairs (0,1), (2,3), (4,5)... in parallel
3. Repeat: Alternate phases until no swaps occur in a complete pass

Parallelization

In each phase, all comparisons are independent—perfect for SIMD instructions or multi-core processing. With n/2 processors, each phase takes O(1), yielding O(n) total with hardware parallelism.

Cycle Sort

Cycle Sort minimizes the number of memory writes by placing each element directly in its final position. It makes the theoretical minimum number of writes—optimal for memory with limited write cycles like flash/EEPROM.

Detailed Algorithm

1. For Each Position: Take the element at position i
2. Count Smaller: Count how many elements are smaller (this is its target position)
3. Skip Duplicates: Advance past any equal elements already in place
4. Rotate Cycle: Swap element to target, take displaced element, repeat
5. Complete Cycle: Continue until returning to starting position

Why Minimum Writes?

Each element is written exactly once to its final position (except cycles returning to start). No temporary copies, no swapping back and forth. This is theoretically optimal for write minimization.

Pancake Sort

Pancake Sort uses only one operation: flip the first k elements (like flipping a stack of pancakes with a spatula). It's a famous theoretical problem studied by Bill Gates and others.

Detailed Algorithm

1. Find Maximum: Find the largest unsorted element
2. Flip to Top: Flip to bring the maximum to the top
3. Flip to Position: Flip again to put the maximum in its final position
4. Shrink: Reduce the unsorted range by one
5. Repeat: Continue for all elements

The Pancake Problem

The pancake number P(n) is the minimum number of flips needed to sort any stack of n pancakes. Bill Gates proved P(n) ≤ (5n+5)/3 in 1979. The exact formula remains unknown—it's an open problem in computer science!

Visual Pattern

Watch dramatic prefix reversals as portions of the array flip. The largest element rises to the top (first position), then the whole unsorted portion flips, placing it at the end. Very distinctive compared to swap-based algorithms.

Strand Sort

Strand Sort extracts sorted "strands" (ascending subsequences) from the input and merges them into the output. It's optimized for data with existing sorted runs, achieving near-O(n) on partially sorted input.

Detailed Algorithm

1. Extract Strand: Take the first element. Scan forward, adding any elements larger than the strand's last element
2. Merge: Merge this strand into the output (like Merge Sort's merge step)
3. Remove Strand: Remove extracted elements from input
4. Repeat: Continue until input is empty

Visual Pattern

Watch as sorted "strands" are pulled out of the chaotic input. Each strand is an ascending subsequence that gets woven into the growing sorted output. It looks like untangling a knot—satisfying and organic.

Bitonic Sort

Bitonic Sort first creates "bitonic sequences" (ascending then descending) and merges them with a fixed compare-swap network. Designed for parallel hardware, it has beautiful symmetry.

Key Concept: Bitonic Sequence

A bitonic sequence increases then decreases (or vice versa), like a mountain peak: [1, 4, 6, 8, 7, 3, 2]. Any bitonic sequence can be split into two bitonic sequences, each smaller than the original.

Detailed Algorithm

1. Build Bitonic: Recursively create bitonic sequences by sorting halves in opposite directions
2. Bitonic Merge: Merge two sorted sequences (one ascending, one descending) into one sorted sequence
3. Compare-Swap: The merge uses parallel compare-swap operations at decreasing distances

Stooge Sort

Stooge Sort is intentionally inefficient—slower than Bubble Sort! It recursively sorts 2/3 of the array three times. Named after the Three Stooges for its comedically bad performance.

Detailed Algorithm

1. Base Case: If first element > last element, swap them
2. Recurse (if ≥3 elements):
   • Stooge sort the first 2/3
   • Stooge sort the last 2/3
   • Stooge sort the first 2/3 again

Why So Slow?

The recurrence T(n) = 3T(2n/3) + O(1) solves to O(n^log₃/₂(3)) = O(n^2.71). This is worse than O(n²)! The triple overlapping recursion is extremely wasteful.

Bogo Sort

Bogo Sort (Stupid Sort, Monkey Sort, Shotgun Sort) randomly shuffles the array and checks if it's sorted. Repeat until sorted. It's the ultimate example of what NOT to do—with factorial expected time!

Detailed Algorithm

1. Check: Is the array sorted?
2. If Yes: Done!
3. If No: Randomly shuffle the entire array
4. Repeat: Go to step 1

The Math of Chaos

There are n! permutations. Only one is sorted. Each shuffle has 1/n! chance of producing the sorted order. Expected shuffles: n!. For n=10, that's 3,628,800 shuffles on average!

Circle Sort

Circle Sort compares pairs of elements equidistant from the center, then recursively applies to halves. It has an elegant symmetrical structure, comparing (0,n-1), (1,n-2), etc., like drawing a circle.

Detailed Algorithm

1. Outer Pairs: Compare (first, last), (second, second-to-last), etc.
2. Middle: If odd length, compare middle with center
3. Recurse: Apply to left half and right half
4. Repeat: Continue full passes until no swaps occur

Visual Pattern

Watch the "circular" comparison pattern—elements at opposite ends are compared simultaneously, creating a symmetric effect. The recursive splitting then creates smaller circles within circles. Passes repeat until stable.

Antigravity Sort

Antigravity Sort is the whimsical inverse of Gravity Sort—beads "rise" instead of falling. It sorts in descending order by having values "float up" like helium balloons. A playful educational variation!

Concept

While Gravity Sort lets beads fall (larger values sink to bottom = ascending order), Antigravity Sort makes beads rise (larger values float to top = descending order, then reversed for ascending).

Analytics Tab

The Analytics tab provides deeper insights into algorithm performance through interactive charts, session statistics, and an algorithm encyclopedia for reference.

Complexity Comparison Chart

An interactive chart comparing all algorithms across multiple dimensions:

• Time Complexity: Color-coded bars showing best, average, and worst case complexities
• Space Complexity: Memory requirements for each algorithm
• Stability: Visual indicators of which algorithms are stable
• Filtering: Toggle between complexity classes (O(n), O(n log n), O(n²))

Session Statistics

Track your learning progress and experimentation:

• Total sorts run in this session
• Total comparisons and swaps observed
• Most-used algorithms
• Average array sizes tested
• Time spent in each mode

Algorithm Encyclopedia

Quick reference cards for each algorithm with key facts:

• Inventor/Year of discovery
• Complexity summary
• Key properties (stable, adaptive, in-place)
• Real-world applications
• Links to academic papers

Data Export

Export your session data for further analysis or archival:

• Session Report (PDF): Formatted summary of your session
• Raw Data (JSON): Complete session data for programmatic analysis
• Comparison Table (CSV): Algorithm comparisons in spreadsheet format

Complexity Guide

Understanding Big O notation is fundamental to evaluating sorting algorithms. This guide explains what the complexity values mean and how they affect real-world performance.

Big O Notation Basics

Big O describes how an algorithm's resource usage scales with input size n:

Real-World Impact

At what point does complexity matter? Consider sorting n elements:

Space Complexity

Memory usage is equally important, especially for large datasets:

Stability Explained

A sorting algorithm is stable if elements with equal keys maintain their original relative order after sorting. This seems like a minor property, but it's crucial for multi-key sorting and database operations.

What Stability Means

Given an array of people sorted by name, if you then sort by age with a stable sort, people of the same age remain alphabetically ordered:

Alice, 25
Bob, 30
Carol, 25
Dave, 30

Alice, 25
Carol, 25
Bob, 30
Dave, 30

Carol, 25
Alice, 25
Dave, 30
Bob, 30

Why Stability Matters

• Multi-key sorting: Sort by secondary key first, then primary key (preserves secondary order)
• Database operations: SQL ORDER BY often needs stable behavior
• User expectations: "Sort by date" shouldn't randomize items with the same date
• Incremental updates: Adding new items and resorting shouldn't scramble existing order

Stable vs Unstable Algorithms

Choosing an Algorithm

No single sorting algorithm is best for all situations. Use this decision guide to select the right tool for your specific requirements.

Quick Decision Tree

By Use Case

Performance vs Simplicity Trade-off

Summary Recommendations