Bubble Sort Algorithm

Idea: Repeatedly go through the list, compare every pair of adjacent elements, and swap
them if they’re in the wrong order. After each full pass, the largest remaining element
“bubbles” to the end. Keep doing passes until the list is sorted.
Steps (with early-exit optimization):
1. Set a flag swapped = true.
2. While swapped is true:
o Set swapped = false.
o From index 0 to n-2 (or up to n-2-pass if you count passes), compare A[j] and
A[j+1].
o If A[j] > A[j+1], swap them and set swapped = true.
3. If in a full pass no swaps happened (swapped stayed false), the list is already sorted →
stop.
Pseudocode (0-based indexing):
bubbleSort(A):
n = length(A)
repeat
swapped = false
for j = 0 to n-2
if A[j] > A[j+1]
swap A[j], A[j+1]
swapped = true
n = n - 1 // last element is in place; next pass can ignore it
until swapped == false
Notes:
• In-place (uses constant extra space).
• Stable (equal elements keep original order).
• Adaptive with early exit (stops early if already sorted).
Easy example (6 numbers), solved step by step
Input: [5, 1, 4, 2, 8, 3]
Pass 1 (compare up to index 4):
• (5,1) → swap → [1, 5, 4, 2, 8, 3]
• (5,4) → swap → [1, 4, 5, 2, 8, 3]
• (5,2) → swap → [1, 4, 2, 5, 8, 3]
• (5,8) → ok → [1, 4, 2, 5, 8, 3]
• (8,3) → swap → [1, 4, 2, 5, 3, 8] (now 8 is fixed at the end)
Pass 2 (compare up to index 3):
• (1,4) → ok → [1, 4, 2, 5, 3, 8]
• (4,2) → swap → [1, 2, 4, 5, 3, 8]
• (4,5) → ok → [1, 2, 4, 5, 3, 8]
• (5,3) → swap → [1, 2, 4, 3, 5, 8] (now 5 is fixed)
Pass 3 (compare up to index 2):
• (1,2) → ok → [1, 2, 4, 3, 5, 8]
• (2,4) → ok → [1, 2, 4, 3, 5, 8]
• (4,3) → swap → [1, 2, 3, 4, 5, 8] (now 4 is fixed)
Pass 4 (compare up to index 1):
• (1,2) → ok
• (2,3) → ok
No swaps in this pass ⇒ stop (early exit).
Output: [1, 2, 3, 4, 5, 8]

Time complexity (with clear counts)

Let n be the number of elements.
Without early-exit (plain Bubble Sort)
• Comparisons:
(n-1) + (n-2) + … + 1 = n(n-1)/2 = Θ(n²)
 • Swaps:
o Worst case (reverse sorted): every comparison swaps → n(n-1)/2 = Θ(n²)
o Average case (random order): expected inversions ≈ n(n-1)/4 → swaps ≈
Θ(n²)
o Best case (already sorted): 0 swaps, but you still do all comparisons → Θ(n²)
Time: Best Θ(n²), Average Θ(n²), Worst Θ(n²)
With early-exit optimization (recommended)
• Best case (already sorted):
One pass, (n-1) comparisons, 0 swaps → Θ(n)
• Average case:
Still ~ half the pairs out of order; comparisons ≈ n(n-1)/2, swaps ≈ n(n-1)/4 → Θ(n²)
• Worst case (reverse sorted):
Comparisons n(n-1)/2, swaps n(n-1)/2 → Θ(n²)
Space complexity: O(1) extra space.
Stability: Stable.
When to use: Good for teaching and very small arrays; not efficient for large inputs.
 Selection Sort Algorithm
Idea:
In every pass, find the smallest element from the unsorted part of the list and place it at the
beginning of that part. After each pass, the sorted portion grows by one, from left to right.
Steps:
1. Start with the first element (index 0).
2. Find the smallest element in the entire list (from index 0 to n–1).
3. Swap it with the first element.
4. Move to the next index (index 1).
5. Find the smallest element from index 1 to n–1.
6. Swap it with element at index 1.
7. Repeat until the list is sorted.
Pseudocode (0-based indexing):
selectionSort(A):
n = length(A)
for i = 0 to n-2
minIndex = i
for j = i+1 to n-1
if A[j] < A[minIndex]
minIndex = j
swap A[i], A[minIndex]
Notes:
• Always does (n-1)+(n-2)+...+1 = n(n-1)/2 comparisons, regardless of input order.
• At most n-1 swaps (much fewer than Bubble Sort).
• Not stable (can break the order of equal elements).
• In-place (O(1) extra space).
Easy example (6 numbers), step by step
Input: [29, 10, 14, 37, 14, 3]
Pass 1 (i=0):
• Smallest element from [29,10,14,37,14,3] is 3 at index 5.
• Swap with index 0.
• List: [3, 10, 14, 37, 14, 29]
Pass 2 (i=1):
• Smallest from [10,14,37,14,29] is 10 at index 1.
• Already in place, no swap.
• List: [3, 10, 14, 37, 14, 29]
Pass 3 (i=2):
• Smallest from [14,37,14,29] is 14 at index 2.
• Already in place.
• List: [3, 10, 14, 37, 14, 29]
Pass 4 (i=3):
• Smallest from [37,14,29] is 14 at index 4.
• Swap with index 3.
• List: [3, 10, 14, 14, 37, 29]
Pass 5 (i=4):
• Smallest from [37,29] is 29 at index 5.
• Swap with index 4.
• List: [3, 10, 14, 14, 29, 37]
Final Output: [3, 10, 14, 14, 29, 37]

Time Complexity
Let n = number of elements.
• Comparisons:
Always (n-1)+(n-2)+...+1 = n(n-1)/2 = Θ(n²)
(independent of input order).
 • Swaps:
o At most n-1 swaps (one per pass).
o Fewer swaps than Bubble Sort.
• Best case:
o List already sorted.
o Still Θ(n²) comparisons, only 0 swaps.
• Average case:
o Random order.
o Θ(n²) comparisons, ~n swaps.
• Worst case:
o Reverse sorted.
o Still Θ(n²) comparisons, n-1 swaps.
Space Complexity: O(1)
Stability: Not stable
Use case: Suitable when swaps are very expensive (e.g., writing to slow memory), because it
minimizes swaps.
 Insertion Sort Algorithm
Idea:
Insertion Sort builds the sorted list one element at a time.
Take the current element and insert it into the correct position among the already sorted
elements on its left. Shift elements to the right if needed.
Steps:
1. Assume the first element is already sorted.
2. Pick the next element (key).
3. Compare it with elements in the sorted portion (to its left).
4. Shift all larger elements one step to the right.
5. Place the key in its correct position.
6. Repeat for all elements until the list is sorted.
Pseudocode (0-based indexing):
insertionSort(A):
n = length(A)
for i = 1 to n-1
key = A[i]
j=i-1
while j >= 0 and A[j] > key
A[j+1] = A[j] // shift right
j=j-1
A[j+1] = key
Notes:
• In-place (no extra array).
• Stable (equal elements keep order).
• Adaptive (works fast on nearly sorted data).
Easy example (6 numbers), step by step
Input: [12, 11, 13, 5, 6, 7]
Pass 1 (i=1, key=11):
• Compare with 12 → 11 < 12 → shift 12 right.
• Insert 11 at start.
• List: [11, 12, 13, 5, 6, 7]
Pass 2 (i=2, key=13):
• Compare with 12 → 13 > 12 → stays.
• List: [11, 12, 13, 5, 6, 7]
Pass 3 (i=3, key=5):
• Compare with 13 → shift right.
• Compare with 12 → shift right.
• Compare with 11 → shift right.
• Insert 5 at index 0.
• List: [5, 11, 12, 13, 6, 7]
Pass 4 (i=4, key=6):
• Compare with 13 → shift.
• Compare with 12 → shift.
• Compare with 11 → shift.
• Compare with 5 → stop (since 5 < 6).
• Insert 6 after 5.
• List: [5, 6, 11, 12, 13, 7]
Pass 5 (i=5, key=7):
• Compare with 13 → shift.
• Compare with 12 → shift.
• Compare with 11 → shift.
• Compare with 6 → stop.
• Insert 7 after 6.
• List: [5, 6, 7, 11, 12, 13]
Final Output: [5, 6, 7, 11, 12, 13]

Time Complexity
Let n = number of elements.
• Best case (already sorted):
Only 1 comparison per element → Θ(n)
• Average case:
Each new element goes halfway back on average → about n²/4 shifts → Θ(n²)
• Worst case (reverse sorted):
Each new element shifts all previous ones → about n(n-1)/2 shifts → Θ(n²)
• Space complexity: O(1) (in-place).
• Stability: Stable.
• Use case: Good for small arrays or when data is almost sorted (e.g., after small
updates).
 Merge Sort Algorithm
Idea:
Merge Sort uses the Divide and Conquer method.
• Divide: Split the list into two halves.
• Conquer: Recursively sort each half.
• Combine: Merge the two sorted halves into a single sorted list.
Steps:
1. If the list has 0 or 1 element → already sorted.
2. Otherwise:
o Divide the list into two halves.
o Recursively call Merge Sort on the left half.
o Recursively call Merge Sort on the right half.
o Merge the two sorted halves.
Pseudocode:
mergeSort(A):
if length(A) > 1:
mid = length(A) // 2
left = A[0 : mid]
right = A[mid : end]
mergeSort(left)
mergeSort(right)
merge(left, right, A) // combine into sorted A
Merging two sorted lists:
• Compare first elements of both.
• Place the smaller one into the result.
• Move pointer forward in that list.
• Repeat until both lists are empty.
Notes:
• Recursive.
• Stable.
• Needs extra memory for merging.
Easy Example (6 numbers), step by step
Input: [38, 27, 43, 3, 9, 82]
Step 1: Divide:
Split into [38, 27, 43] and [3, 9, 82]
Step 2: Sort left [38, 27, 43]:
• Split → [38] and [27, 43]
• [38] is already sorted
• Sort [27, 43] → split into [27], [43] → merge → [27, 43]
• Merge [38] and [27, 43]:
o Compare 38 and 27 → take 27
o Compare 38 and 43 → take 38
o Then take 43
o Result: [27, 38, 43]
Step 3: Sort right [3, 9, 82]:
• Split → [3] and [9, 82]
• [3] is already sorted
• Sort [9, 82] → split → [9], [82] → merge → [9, 82]
• Merge [3] and [9, 82]:
o Compare 3 and 9 → take 3
o Then take 9 and 82
o Result: [3, 9, 82]
Step 4: Merge two halves [27, 38, 43] and [3, 9, 82]:
• Compare 27 and 3 → take 3
• Compare 27 and 9 → take 9
• Compare 27 and 82 → take 27
• Compare 38 and 82 → take 38
• Compare 43 and 82 → take 43
• Finally take 82
• Result: [3, 9, 27, 38, 43, 82]
Sorted Output: [3, 9, 27, 38, 43, 82]
Time Complexity
Let n = number of elements.
• Best case:
Every split is log n, merging takes n per level.
→ Θ(n log n)
• Average case:
Always divides into halves, merges at each level.
→ Θ(n log n)
• Worst case:
Same structure, still Θ(n log n)
• Space complexity: O(n) (needs temporary arrays during merge).
• Stability: Stable.
• Use case: Good for large data, external sorting (like files on disk).
 Quick Sort Algorithm
Idea:
Quick Sort also uses Divide and Conquer, but instead of merging, it works by partitioning:
• Pick a pivot element.
• Rearrange the array so that all elements smaller than pivot come before it, and all
greater than pivot come after it.
• Pivot goes into its correct sorted position.
• Recursively apply Quick Sort on left and right parts.
Steps:
1. If the array has 0 or 1 element → already sorted.
2. Choose a pivot (commonly first element, last element, or middle).
3. Partition the array into two parts around the pivot.
4. Recursively apply Quick Sort on both parts.
Pseudocode (using last element as pivot):
quickSort(A, low, high):
if low < high:
p = partition(A, low, high) // pivot position
quickSort(A, low, p-1) // left side
quickSort(A, p+1, high) // right side

partition(A, low, high):

pivot = A[high]
i = low - 1
for j = low to high-1:
if A[j] <= pivot:
i=i+1
swap A[i], A[j]
swap A[i+1], A[high]
return i+1 // pivot index
Notes:
• In-place (needs little extra memory).
 • Not stable (unless modified).
• Works very fast on average.

Easy Example (6 numbers), step by step

Input: [10, 7, 8, 9, 1, 5]
Pivot choice = last element.
Step 1: Partition (low=0, high=5, pivot=5):
• Compare each element with 5:
o 10 > 5 → ignore
o 7 > 5 → ignore
o 8 > 5 → ignore
o 9 > 5 → ignore
o 1 ≤ 5 → swap with first position → [1, 7, 8, 9, 10, 5]
• Place pivot (5) in correct position → [1, 5, 8, 9, 10, 7]
Pivot index = 1
Now two parts: [1] and [8, 9, 10, 7]

Step 2: Left [1] → already sorted.

Step 3: Right [8, 9, 10, 7] (low=2, high=5, pivot=7):
• Compare with 7:
o 8 > 7 → ignore
o 9 > 7 → ignore
o 10 > 7 → ignore
• No swaps. Place pivot → [1, 5, 7, 9, 10, 8]
Pivot index = 2
Now parts: [ ] and [9, 10, 8]

Step 4: Right [9, 10, 8] (pivot=8):

• Compare with 8:
o 9 > 8 → ignore
o 10 > 8 → ignore
 • Place pivot → [1, 5, 7, 8, 10, 9]
Pivot index = 3
Now parts: [ ] and [10, 9]

Step 5: Right [10, 9] (pivot=9):

• Compare with 9:
o 10 > 9 → ignore
• Place pivot → [1, 5, 7, 8, 9, 10]
Final Output: [1, 5, 7, 8, 9, 10]

Time Complexity
Let n = number of elements.
• Best case (balanced partition):
Each partition divides roughly in half.
→ Θ(n log n)
• Average case:
Random pivot gives ~balanced partitions on average.
→ Θ(n log n)
• Worst case (unbalanced partition):
If pivot is always smallest or largest (e.g., already sorted with bad pivot choice),
→ Θ(n²)
• Space complexity:
o In-place partitioning: O(log n) (for recursion stack in best/average)
o Worst case recursion depth: O(n)
• Stability: Not stable.
• Use case: Very efficient for large datasets in memory, faster than Merge Sort in
practice.
 Shell Sort Algorithm
Idea:
Shell Sort is an improved version of Insertion Sort.
• In Insertion Sort, elements move only one position at a time.
• Shell Sort lets elements move farther in one step by comparing elements that are gap
positions apart.
• Start with a large gap, keep reducing the gap, and finally use gap = 1 (normal Insertion
Sort).
• By then, the list is almost sorted, so Insertion Sort becomes very fast.
Steps:
1. Choose a sequence of gaps (e.g., n/2, n/4, …, 1).
2. For each gap:
o Perform a gapped insertion sort on elements that are gap apart.
3. Repeat until gap = 1.
Pseudocode:
shellSort(A):
n = length(A)
gap = n // 2
while gap > 0:
for i = gap to n-1:
key = A[i]
j=i
while j >= gap and A[j-gap] > key:
A[j] = A[j-gap]
j = j - gap
A[j] = key
gap = gap // 2
Notes:
• In-place, no extra memory.
• Not stable (can break equal elements’ order).
• The efficiency depends on the gap sequence used.
Easy Example (6 numbers), step by step
Input: [23, 12, 1, 8, 34, 54]
Let’s use gap sequence: n/2 = 3, then 1.
Pass 1 (gap=3):
Compare elements 3 apart → pairs: (23,8), (12,34), (1,54)
• Compare 23 and 8 → swap → [8, 12, 1, 23, 34, 54]
• (12,34) already sorted
• (1,54) already sorted
List after gap=3: [8, 12, 1, 23, 34, 54]
Pass 2 (gap=1 = Insertion Sort):
Now do normal insertion sort.
• (8,12) okay
• 1 < 12 → shift → [8, 12, 12, 23, 34, 54] → [8, 8, 12, 23, 34, 54] → [1, 8, 12, 23, 34,
54]
• (23) okay
• (34) okay
• (54) okay
Final Output: [1, 8, 12, 23, 34, 54]

Time Complexity
Shell Sort’s time depends heavily on the gap sequence used.
• Worst case:
o Using simple gap sequence (n/2, n/4, …, 1): Θ(n²)
o Using better gap sequences (e.g., Hibbard, Sedgewick): about Θ(n^(3/2)) or
better.
• Best case (already sorted):
o With gap = n/2, then n/4, etc., comparisons but no shifts → Θ(n log n) to Θ(n)
(depending on gap sequence).
• Average case:
o Typically between Θ(n log n) and Θ(n^(3/2)).
o Much faster than Insertion Sort for medium/large arrays.
Space complexity: O(1) (in-place).
Stability: Not stable.
Use case: Faster than Bubble/Insertion/Selection for moderate input sizes, but usually
replaced by Merge/Quick/Heap in practice.

Heap Sort Algorithm

Idea:
Heap Sort uses a binary heap (complete binary tree stored in an array).
• First, build a max heap so the largest element is at the root (index 0).
• Swap the root with the last element (puts largest in correct position).
• Reduce the heap size by 1 and heapify the root to restore heap property.
• Repeat until only one element remains.
Steps:
1. Build a max heap from the array.
2. For i = n-1 down to 1:
o Swap A[0] (max) with A[i].
o Reduce heap size by 1.
o Heapify the root.
Pseudocode (0-based indexing):
heapSort(A):
n = length(A)

// Step 1: build max heap

for i = n//2 - 1 down to 0:
heapify(A, n, i)

// Step 2: extract elements

for i = n-1 down to 1:
swap A[0], A[i] // move max to end
heapify(A, i, 0) // fix heap
heapify(A, n, i):
largest = i
left = 2*i + 1
right = 2*i + 2

if left < n and A[left] > A[largest]:

largest = left
if right < n and A[right] > A[largest]:
largest = right

if largest != i:
swap A[i], A[largest]
heapify(A, n, largest)
Notes:
• In-place (no extra memory).
• Not stable.
• Always O(n log n) time.

Easy Example (6 numbers), step by step

Input: [4, 10, 3, 5, 1, 2]
Step 1: Build Max Heap
Turn array into heap (max element at root).
Resulting max heap: [10, 5, 4, 1, 3, 2]
Step 2: Extract elements one by one
• Swap 10 and 2 → [2, 5, 4, 1, 3, 10] → heapify → [5, 3, 4, 1, 2, 10]
• Swap 5 and 2 → [2, 3, 4, 1, 5, 10] → heapify → [4, 3, 2, 1, 5, 10]
• Swap 4 and 1 → [1, 3, 2, 4, 5, 10] → heapify → [3, 1, 2, 4, 5, 10]
• Swap 3 and 2 → [2, 1, 3, 4, 5, 10] → heapify → [2, 1, 3, 4, 5, 10]
• Swap 2 and 1 → [1, 2, 3, 4, 5, 10]
Sorted Output: [1, 2, 3, 4, 5, 10]
Time Complexity
Let n = number of elements.
• Building heap: O(n)
• Heapify per element: O(log n)
• Total for n elements: O(n log n)
• Best case: O(n log n) (same as worst).
• Average case: O(n log n)
• Worst case: O(n log n)
Space complexity: O(1) (in-place).
Stability: Not stable.
Use case: Good when worst-case guarantees are required, but slower in practice than Quick
Sort due to constant factors.
 Radix Sort Algorithm
Idea:
Radix Sort sorts numbers digit by digit.
• Start from the least significant digit (LSD) (units place).
• Use a stable sorting algorithm (like Counting Sort) to sort numbers by that digit.
• Move to the next digit (tens, hundreds, …).
• Continue until the most significant digit is sorted.
Because it processes digits in order and uses a stable sort each time, the whole array becomes
sorted.
Steps (LSD version):
1. Find the maximum number to know how many digits are needed.
2. For digit place = 1 (units), 10 (tens), 100 (hundreds), … up to the max digit:
o Apply Counting Sort based on the current digit.
Pseudocode (base 10 example):
radixSort(A):
maxNum = maximum(A)
exp = 1 // digit place (1=units, 10=tens, ...)
while maxNum // exp > 0:
countingSortByDigit(A, exp)
exp = exp * 10

countingSortByDigit(A, exp):
n = length(A)
output = array of size n
count = array[0..9] = 0

// count digit occurrences

for i = 0 to n-1:
digit = (A[i] // exp) % 10
count[digit]++
 // prefix sum to get positions
for i = 1 to 9:
count[i] += count[i-1]

// build output array (stable)

for i = n-1 downto 0:
digit = (A[i] // exp) % 10
output[count[digit]-1] = A[i]
count[digit]--

// copy back to A
for i = 0 to n-1:
A[i] = output[i]
Notes:
• Requires a stable sub-sort (Counting Sort).
• Works best when number of digits is small compared to n.
• Non-comparison-based.

Easy Example (6 numbers), step by step

Input: [170, 45, 75, 90, 802, 24]
Step 1: Units digit (exp=1):
Sort by last digit → [170, 90, 802, 24, 45, 75]
Step 2: Tens digit (exp=10):
Sort by tens → [802, 24, 45, 75, 170, 90]
Step 3: Hundreds digit (exp=100):
Sort by hundreds → [24, 45, 75, 90, 170, 802]
Final Output: [24, 45, 75, 90, 170, 802]
Time Complexity
Let:
• n = number of elements
• d = number of digits in the maximum number
• k = range of digit values (for decimal, k=10)
• Each digit sort (Counting Sort): O(n + k)
• Total: O(d * (n + k))
Cases:
• Best case: O(d * (n + k))
• Average case: O(d * (n + k))
• Worst case: O(d * (n + k))
(Unlike comparison sorts, all three are the same.)
Space complexity: O(n + k) (extra arrays).
Stability: Stable (if stable sub-sort is used).
Use case: Very fast for integers or strings with limited digit length (like sorting phone
numbers, zip codes).
 Counting Sort Algorithm (exam-ready, easy words)
Idea:
Counting Sort doesn’t compare elements. Instead, it:
• Counts how many times each number occurs.
• Uses this information to place numbers directly in their correct position.
It works only when the range of input values (0…k) is not too large compared to n.
Steps:
1. Find the maximum value maxVal in the array.
2. Create a count[] array of size maxVal+1, initialized with 0.
3. Count each element: For every number A[i], do count[A[i]]++.
4. Modify count[] to store prefix sums (cumulative counts). This tells the final positions.
5. Build the output array by placing each element in its correct position (stable way:
iterate input from right to left).
6. Copy output back into the original array.
Pseudocode:
countingSort(A):
n = length(A)
maxVal = maximum(A)
count = array[0..maxVal] = 0
output = array of size n

// Step 1: count occurrences

for i = 0 to n-1:
count[A[i]]++

// Step 2: prefix sum

for i = 1 to maxVal:
count[i] += count[i-1]

// Step 3: build output (stable)

for i = n-1 downto 0:
 output[count[A[i]]-1] = A[i]
count[A[i]]--

// Step 4: copy back

for i = 0 to n-1:
A[i] = output[i]

Easy Example (6 numbers), step by step

Input: [4, 2, 2, 8, 3, 3]
Step 1: Find max = 8 → count[0..8]
Step 2: Count occurrences:
count = [0,0,2,2,1,0,0,0,1]
(index = value)
Step 3: Prefix sum:
count = [0,0,2,4,5,5,5,5,6]
Now, count[i] tells how many numbers ≤ i exist.
Step 4: Place elements (iterate from right):
• 3 → position count[3]=4 → output[3]=3 → count[3]--
• 3 → position count[3]=3 → output[2]=3 → count[3]--
• 8 → position count[8]=6 → output[5]=8 → count[8]--
• 2 → position count[2]=2 → output[1]=2 → count[2]--
• 2 → position count[2]=1 → output[0]=2 → count[2]--
• 4 → position count[4]=5 → output[4]=4 → count[4]--
Output: [2, 2, 3, 3, 4, 8]
Time Complexity
Let:
• n = number of elements
• k = range of input values (max element)
• Counting elements = O(n)
• Prefix sum = O(k)
• Building output = O(n)
Total: O(n + k)
Cases:
• Best case: O(n + k)
• Average case: O(n + k)
• Worst case: O(n + k)
Space complexity: O(n + k) (output + count array).
Stability: Stable (if built carefully, as shown).
Use case: Small integers, grades, IDs, frequencies, when k is not huge.
 Bucket Sort Algorithm
Idea:
• Bucket Sort works by distributing elements into buckets (groups) based on their
value range.
• Then, each bucket is sorted individually (using another algorithm like Insertion Sort).
• Finally, all buckets are combined to get the sorted array.
It works best when the input numbers are uniformly distributed (e.g., floating-point
numbers between 0 and 1).
Steps:
1. Create k empty buckets (lists).
2. Distribute each element of the input array into a bucket based on its value.
o Example: If numbers are between 0 and 1, element x goes into bucket index
floor(k*x).
3. Sort each non-empty bucket (usually Insertion Sort).
4. Concatenate all buckets in order to get the final sorted array.
Pseudocode:
bucketSort(A):
n = length(A)
k = number of buckets
buckets = array of k empty lists

// Step 1: distribute
for i = 0 to n-1:
index = floor(k * A[i]) // assuming 0 ≤ A[i] < 1
insert A[i] into buckets[index]

// Step 2: sort each bucket

for i = 0 to k-1:
sort(buckets[i]) // often Insertion Sort
 // Step 3: concatenate
return all elements of buckets in order

Easy Example (6 numbers)

Input: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94]
Assume k = 5 buckets (index 0–4).
Step 1: Distribute into buckets:
• 0.78 → bucket[3]
• 0.17 → bucket[0]
• 0.39 → bucket[1]
• 0.26 → bucket[1]
• 0.72 → bucket[3]
• 0.94 → bucket[4]
Now buckets look like:
bucket[0] = [0.17]
bucket[1] = [0.39, 0.26]
bucket[2] = []
bucket[3] = [0.78, 0.72]
bucket[4] = [0.94]
Step 2: Sort each bucket individually:
• bucket[0] = [0.17]
• bucket[1] = [0.26, 0.39]
• bucket[3] = [0.72, 0.78]
• bucket[4] = [0.94]
Step 3: Concatenate buckets:
[0.17, 0.26, 0.39, 0.72, 0.78, 0.94]
Time Complexity
Let:
• n = number of elements
• k = number of buckets
• Distribution into buckets: O(n)
• Sorting buckets: depends on bucket contents
Cases:
• Best case (uniform distribution, small bucket size): O(n + k) ≈ O(n)
• Average case: O(n + k) ≈ O(n)
• Worst case (all elements in one bucket): O(n²) (if Insertion Sort is used inside).
Space complexity: O(n + k) (for buckets).
Stability: Depends on the sorting algorithm used inside buckets.
Crucial terms for sorting algorithms

1) Stable Sort
Definition:
• A sorting algorithm is stable if it preserves the relative order of equal elements.
Example:
Input (name, age): [ (Alice, 25), (Bob, 20), (Charlie, 25) ]
Sort by age (ascending):
- Stable sort → [ (Bob, 20), (Alice, 25), (Charlie, 25) ] // Alice before Charlie
- Unstable sort → [ (Bob, 20), (Charlie, 25), (Alice, 25) ] // order changed
Key point:
• Important when elements have multiple attributes and you sort on one of them.

2) In-Place Sort
Definition:
• A sorting algorithm is in-place if it uses only a constant amount of extra memory
(not counting recursion stack).
• Typically uses O(1) extra space.
Example:
• Bubble Sort, Insertion Sort, Quick Sort → in-place
• Merge Sort, Counting Sort, Bucket Sort → not in-place (needs extra arrays)
Key point:
• Saves memory, useful for large datasets in limited memory.

3) Time Complexity Terms

• Best Case: The minimum time the algorithm takes on any input.
o Example: Bubble Sort → already sorted → O(n)
• Average Case: The expected time on a random input.
o Example: Insertion Sort → random array → O(n²)
• Worst Case: The maximum time the algorithm takes on any input.
o Example: Quick Sort → already sorted array with bad pivot → O(n²)
Why important:
• Exams often ask “best, average, worst” separately.

4) Space Complexity
• Memory used by an algorithm.
• Includes extra arrays, recursion stack, temporary storage.
Example:
• Heap Sort → O(1) extra space (in-place)
• Merge Sort → O(n) extra space

5) Adaptive Algorithm
• An algorithm is adaptive if it performs better on partially sorted data.
Example:
• Insertion Sort → almost sorted array → faster than O(n²)
• Bubble Sort (optimized with flag) → detects sorted array

6) Comparison-Based vs Non-Comparison-Based
• Comparison-Based: Algorithm compares elements to sort.
o Bubble, Selection, Insertion, Merge, Quick, Heap → Ω(n log n) lower bound
• Non-Comparison-Based: Uses other properties like counting, digit, or range.
o Counting Sort, Radix Sort, Bucket Sort → can achieve O(n)

7) Divide and Conquer

• Strategy: Divide problem into smaller subproblems, solve them recursively, combine
results.
Example:
• Merge Sort → divide array → merge
• Quick Sort → divide array via pivot → sort subarrays
8) Other Useful Terms
Term Meaning / Example
Gapped / Interval Sort Used in Shell Sort — elements compared are gap apart
Heap Property Max-heap → parent ≥ children; Min-heap → parent ≤
children
Recursive / Iterative Recursive → function calls itself (Merge/Quick), Iterative →
uses loops (Bubble/Insertion)
Prefix Sum Cumulative sum array, used in Counting Sort to find positions
Stable Subroutine When a stable internal sort is used, like Counting Sort in
Radix Sort

Sorting Best Average Worst Space Stable In- Notes / Use

Algorithm Case Case Case Comple Place Case
Time Time Time xity
Bubble O(n) O(n²) O(n²) O(1) Yes Yes Simple,
Sort adaptive if
optimized
Selection O(n²) O(n²) O(n²) O(1) No Yes Simple,
Sort always does
n²
comparisons
Insertion O(n) O(n²) O(n²) O(1) Yes Yes Adaptive,
Sort fast for
nearly
sorted
arrays
Merge O(n log O(n log n) O(n log n) O(n) Yes No Divide &
Sort n) conquer,
good for
large data,
external
sorting
Quick O(n log O(n log n) O(n²) O(log n) No Yes Fast in
Sort n) (stack) practice,
careful
pivot
selection
 avoids
worst case
Heap Sort O(n log O(n log n) O(n log n) O(1) No Yes In-place,
n) worst-case
guarantee,
uses heap
structure
Shell Sort O(n log O(n^(3/2)) O(n²) O(1) No Yes Gap-based
n) typical insertion
(depends sort,
on gap) efficient for
medium
arrays
Counting O(n + k) O(n + k) O(n + k) O(n + k) Yes No Non-
Sort comparison
sort, small
integer
range, stable
Radix O(d*(n O(d*(n + O(d*(n + O(n + k) Yes No Non-
Sort + k)) k)) k)) comparison
sort, sorts
digits, often
uses
Counting
Sort
internally
Bucket O(n + k) O(n + k) O(n²) (all O(n + k) Depends No Uniformly
Sort in one on sub- distributed
bucket) sort numbers,
divide into
buckets, sort
each

Key to Table:
• n = number of elements
• k = range of input numbers (Counting, Radix, Bucket)
• d = number of digits (Radix Sort)
Quick tips:
1) Best for Small Arrays (n < 20–50)
Algorithm Why
Insertion Sort Very fast on small arrays, adaptive if nearly sorted, stable, in-place
Bubble Sort Simple to implement, adaptive if optimized
Selection Sort Simple, predictable, but always O(n²)
Tip: Small arrays → simplicity > efficiency

2) Best for Large Arrays (n >> 50)

Algorithm Why
Merge Sort Always O(n log n), stable, good for external sorting, predictable
Quick Sort Very fast on average, in-place, use randomized pivot to avoid O(n²)
Heap Sort In-place, always O(n log n), worst-case guarantee
Tip: Large arrays → prefer O(n log n) algorithms

3) Best for Nearly Sorted Arrays

Algorithm Why
Insertion Sort Adaptive → O(n) for sorted/near-sorted data
Bubble Sort Adaptive if you add a flag to detect sorted array
Shell Sort Gap-based movement helps reduce large inversions quickly
Tip: If array is “almost sorted,” avoid heavy O(n log n) sorts; adaptive sorts are better

4) Best for Special Cases

Algorithm Best Use Case
Counting Small integers or grades, limited range, stable
Sort
Radix Sort Integers or strings, multiple digits, stable
Bucket Sort Floating-point numbers uniformly distributed, stable depending on sub-
sort
Tip: Non-comparison sorts → O(n) possible, but extra memory needed
5) Space Considerations
Algorithm Space
In-place (O(1)) Bubble, Selection, Insertion, Quick, Heap, Shell
Extra space needed (O(n)) Merge, Counting, Radix, Bucket

Exam Shortcut:
• Stable & in-place → good for linked lists or memory-limited, maintain order.
• Adaptive → best for nearly sorted.
• Divide & Conquer → fast for large arrays.
• Non-comparison → integer/string sorting, O(n).