Searching & Sorting Performance Lab
Run sorting and searching algorithms step by step on arrays of different sizes and input orders. Count comparisons and swaps, animate each operation, compare two algorithms side by side, and verify theoretical Big-O complexity with real data.
Guided Experiment: O(n²) vs O(n log n)
How will the number of comparisons differ between selection sort and merge sort as array size increases from 10 to 100?
Write your hypothesis in the Lab Report panel, then click Next.
Array
Controls
Results
Select an algorithm, configure the array, and click Run to see performance results.
Data Table
(0 rows)| # | Algorithm | Array Size | Input Type | Comparisons | Swaps | Time(ms) | Complexity |
|---|
Reference Guide
Selection Sort — O(n²)
Selection sort scans the unsorted portion of the array to find the minimum element and swaps it into position. It always performs exactly n(n−1)/2 comparisons regardless of input order.
While simple to implement, its quadratic behavior makes it impractical for large datasets. It does perform at most n−1 swaps, making it useful when writes are expensive.
Insertion Sort — O(n²)
Insertion sort builds the sorted portion one element at a time, shifting larger elements right to make room. Its performance depends heavily on input order.
On already-sorted input, it uses only n−1 comparisons (best case). On reverse-sorted input, it degrades to n(n−1)/2. This adaptive behavior makes it ideal for nearly-sorted data.
Merge Sort — O(n log n)
Merge sort divides the array in half recursively, sorts each half, and merges the sorted halves. It always uses approximately n log₂ n comparisons, regardless of input.
This divide-and-conquer approach guarantees O(n log n) performance but requires O(n) extra space for merging. It is a stable sort, meaning equal elements keep their original order.
Binary Search — O(log n)
Binary search repeatedly halves the search space by comparing the target to the middle element. It requires a sorted array as a precondition.
For n = 1000, binary search needs at most 10 comparisons versus 1000 for linear search. The total cost of sorting first then binary searching is O(n log n) + O(log n), which pays off when multiple searches are needed.