Performance Chart
Head-to-head algorithm battles across categories with performance charts and deep process analysis.
All sorting algorithms race on the same input. Slow algorithms (O(n²)) skipped for inputs > 2000 elements. Winner is determined by execution time.
All search algorithms compete on the same array and target. Measures time, comparisons, and success rate. Binary search family expected to dominate.
| Algorithm | Time (ms) | Complexity | {% if result[0].stable is defined %}Stable | {% endif %} {% if result[0].found is defined %}Found | {% endif %} {% if result[0].comparisons is defined %}Comparisons | {% endif %}
|---|---|---|---|---|---|
| {{ r.name }} | {% if r.time_ms is number and r.time_ms < 999999 %} {{ "%.4f"|format(r.time_ms) }} {% else %} Skipped {% endif %} | {{ r.complexity }} | {% if r.stable is defined %}{{ r.stable }} | {% endif %} {% if r.found is defined %}{{ "Yes" if r.found else "No" }} | {% endif %} {% if r.comparisons is defined %}{{ r.comparisons }} | {% endif %}
Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. Like bubbles rising to the surface — largest elements "bubble up" to their correct position.
Divide-and-conquer: splits array in half recursively until single elements, then merges sorted halves. Guaranteed n log n performance. The merge step compares elements from two sorted subarrays and builds a larger sorted array.
Pick a pivot, partition array into elements less than and greater than pivot, recursively sort partitions. In-place with O(log n) stack space. Fastest in practice for large random datasets. Worst case O(n²) when pivot selection is poor.
Build a max-heap from the array, then repeatedly extract the maximum element and place it at the end. In-place sorting with guaranteed O(n log n) performance. Uses heapify to maintain heap property after each extraction.
Non-comparison based. Count occurrences of each value, compute cumulative counts, then place elements in output array in stable order. Only works for integer ranges. Extremely fast when k (range) is small.
Sorts by processing individual digits from least significant to most significant. Uses counting sort as a subroutine for each digit. Handles large integers efficiently when digit count d is small.
Generalization of insertion sort. Sorts elements that are gap apart, then reduces gap. Final gap of 1 is regular insertion sort. Performance depends on gap sequence (Shell, Knuth, Ciura).
Python's built-in sort. Hybrid of merge sort and insertion sort. Identifies "runs" (already sorted sequences) and merges them. Highly optimized for real-world data with existing order. Best practical performance.
Small arrays (n < 50): Insertion Sort
General purpose: Timsort / Merge Sort
In-place needed: Quick Sort / Heap Sort
Integer range small: Counting / Radix Sort
Stability required: Merge Sort / Timsort
Sequentially checks each element until the target is found or the end is reached. No preprocessing required. Works on unsorted data. Simple but slow for large datasets. Best when data is small or unsorted.
Compare target with middle element. If equal, return. If target is smaller, search left half. Otherwise search right half. Repeat until found or bounds cross. Requires sorted array. The gold standard for sorted data.
Jump ahead by √n steps until finding a block where target could be, then linear search backward. Balance between linear and binary search. Optimal jump size is √n for minimizing comparisons.
Estimates position using linear interpolation: pos = low + ((target - arr[low]) / (arr[high] - arr[low])) * (high - low). Best for uniformly distributed sorted data. Can degrade to O(n) for non-uniform distributions.
Find range where element exists by checking indices 1, 2, 4, 8... (exponential jumps). Then binary search within that range. Useful for unbounded/infinite arrays. First element checked is at index 0.
Divide array into three parts using two midpoints. Eliminate one-third of the search space each iteration. Slightly slower than binary search in practice due to more comparisons, but useful for unimodal function optimization.
Uses Fibonacci numbers to divide array. Find smallest Fibonacci number ≥ n, then compare element at Fibonacci offset. Eliminates ~1/φ (61.8%) of remaining elements. Interesting mathematical property but rarely used in practice.
Unsorted data: Linear Search
Sorted array: Binary Search
Uniform distribution: Interpolation Search
Unknown/infinite size: Exponential Search
Function optimization: Ternary Search
Small array: Linear or Jump Search