Bubble Sort — step-by-step algorithm
1. Let A be the array of n elements.
2. Repeat for i from 0 to n-2 (i.e. perform n-1 passes):
a. For each index j from 0 to n-2-i:
I) Compare A[j] and A[j+1].
II) If A[j] > A[j+1], swap them.
b. After this inner loop, the largest element among A[0..n-1-i] is at position n-1-i.
3. When all passes complete, the array is sorted.
Complexity & properties
Time complexity:
Worst / Average: O(n²)
Best (optimized, already sorted): O(n)
Selection Sort:
Let A be an array of n elements.
For i from 0 to n-2:
a. Assume the minimum element is at index i → min_index = i.
b. For each index j from i+1 to n-1:
o If A[j] < A[min_index], then update min_index = j.
c. After scanning, swap A[i] with A[min_index] (if different).
Repeat until array is sorted.
Time complexity:
Best, Average, Worst: O(n²) (always scans entire array for each pass).
Insertion Sort:
Let A be an array of n elements.
Start from the second element (index 1) and iterate to n-1.
For each i in 1..n-1:
a. Store the current element as key = A[i].
b. Compare key with elements before it (A[0..i-1]).
c. Shift all elements greater than key one position to the right.
d. Insert key into the correct position.
Repeat until the array is sorted.
Time complexity:
Worst & Average: O(n²)
Best (already sorted): O(n)
Comparisons::
Feature Bubble Sort
Selection Sort Insertion Sort
Finds the
Repeatedly swaps
minimum Inserts each element
adjacent elements
element in into its correct position
Basic Idea if they are in wrong
unsorted part among already sorted
order (largest
and puts it at elements.
“bubbles” to end).
correct position.
O(n²) (always
O(n) (with early- O(n) (when already
Best Case Time scans entire
exit optimization) sorted)
array)
Worst Case
O(n²) O(n²) O(n²)
Time
Average Case
O(n²) O(n²) O(n²)
Time
Space
O(1) (in-place) O(1) (in-place) O(1) (in-place)
Complexity
✅ Stable (keeps ❌ Not stable
✅ Stable (keeps equal
Stability equal elements in (can swap equal
elements in order)
order) elements)
✅ Adaptive (with ✅ Adaptive (efficient for
Adaptiveness ❌ Not adaptive
optimization) nearly sorted)
Depends on input; can
Many swaps (after Few swaps (at
Swaps be fewer than bubble
every wrong pair) most n–1)
sort
Easiest to
Simple but less Simple, often faster on
Ease of Use understand
practical small datasets
(teaching tool)
Rare in Used in practice for
Rare in practice,
Practical Use practice, small/nearly-sorted
educational
educational arrays
Quick Sort:
Input: An array A with n elements.
If the array has 0 or 1 element, it is already sorted → return.
Otherwise:
a. Choose a pivot element from the array (commonly first, last, or middle).
b. Partition the array into two sub-arrays:
o Left sub-array: elements less than or equal to pivot
o Right sub-array: elements greater than pivot
c. Recursively apply Quick Sort on the left and right sub-arrays.
d. Combine the results → [sorted left] + [pivot] + [sorted right].
Time complexity:
Best / Average: O(n log n)
Worst (already sorted, bad pivot): O(n²)
Merge Sort:
Input: An array A of n elements.
If n ≤ 1, return (array is already sorted).
Otherwise:
a. Divide the array into two halves:
o Left half → A[0..mid]
o Right half → A[mid+1..n-1]
b. Recursively apply Merge Sort to both halves.
c. Merge the two sorted halves into one sorted array.
Time complexity:
Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)
Radix Sort:
Input: An array A of n integers (non-negative).
Find the maximum number in the array to determine the number of digits d.
For each digit position from least significant digit (LSD) to most significant digit (MSD):
a. Use a stable sorting algorithm (commonly Counting Sort) to sort the array based on the
current digit.
b. After each pass, the array is partially sorted according to that digit.
After processing all digits, the array is completely sorted.
Time complexity: O(d * (n + k))
d = number of digits in max number
k = range of digits (0–9 → constant)
Shall Sort:
Input: An array A of n elements.
Choose an initial gap (commonly n/2).
While gap > 0:
a. For each element i from gap to n-1:
o Save A[i] as temp.
o Compare and shift earlier elements (A[i-gap], A[i-2*gap], …) that are
larger than temp.
o Insert temp at the correct position.
b. Reduce the gap (commonly gap = gap / 2).
When gap = 1, the algorithm performs a final insertion sort pass.
The array is now sorted.
Time complexity:
Worst: between O(n²) and O(n^(3/2)) depending on gap sequence
Best: O(n log n)
Heap Sort:
Input: An array A of n elements.
Build a max heap from the array:
o Start from the last non-leaf node and heapify each node up to the root.
Once the max heap is built:
a. Swap the root (A[0], the largest element) with the last element A[n-1].
b. Reduce heap size by 1 (n = n - 1).
c. Heapify the root again to restore max heap property.
d. Repeat until heap size = 1.
The array is now sorted in ascending order.
Time complexity:
Build heap: O(n)
Heapify operations: O(log n) each
Total: O(n log n) (worst, average, best)