Sorting Algorithms
A Detailed Reference with Step-by-Step Examples
Bubble Sort • Insertion Sort • Selection Sort • Quick Sort • Merge Sort
1. Bubble Sort
Bubble Sort is the simplest comparison-based sorting algorithm. It repeatedly steps through the list,
compares adjacent elements, and swaps them if they are in the wrong order. The largest unsorted
element "bubbles up" to its correct position at the end of the array after each pass.
Key Concepts
• Outer loop controls the number of passes (n-1 total passes needed).
• Inner loop compares adjacent pairs and swaps if needed.
• After each pass, the largest remaining element is placed at the end.
• The inner loop shrinks by 1 each time (n-1-i) because the sorted region at the tail grows.
C Code
void bubbleSort(int arr[], int n){
for(int i=0;i<n-1;i++){
for(int j=0;j<n-1-i;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
Step-by-Step Example
Input array: [64, 34, 25, 12, 22]
Pass Before Pass Action After Pass
Pass 1 [64, 34, 25, 12, 22] Compare & swap until end. 64 [34, 25, 12, 22, 64]
bubbles to position 4.
Pass 2 [34, 25, 12, 22, 64] 34 bubbles to position 3. [25, 12, 22, 34, 64]
Pass 3 [25, 12, 22, 34, 64] 25 bubbles to position 2. [12, 22, 25, 34, 64]
Pass 4 [12, 22, 25, 34, 64] Already in order. No swaps needed. [12, 22, 25, 34, 64] ✓
📊 Complexity:
Time: O(n²) average and worst case | Space: O(1) | Stable: Yes
2. Insertion Sort
Insertion Sort builds a sorted portion of the array from left to right. It picks one element at a time from
the unsorted part and inserts it at the correct position within the sorted part — just like how you sort
playing cards in your hand.
Key Concepts
• The first element is considered already sorted.
• Starting from index 1, each element (key) is compared with elements in the sorted part.
• Larger elements are shifted one position to the right to make room.
• The key is placed in its correct sorted position.
C Code
void insertionSort(int arr[], int n){
for(int i=1;i<n;i++){
int key=arr[i];
int j=i-1;
while(j>=0 && arr[j]>key){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
Step-by-Step Example
Input array: [12, 11, 13, 5, 6]
Step Key Sorted Part Action Array After
(i) Before
i=1 11 [12] 11 < 12 → shift 12 right, [11, 12, 13, 5, 6]
insert 11
i=2 13 [11, 12] 13 > 12 → no shift, insert in [11, 12, 13, 5, 6]
place
i=3 5 [11, 12, 13] 5 < 13, 12, 11 → shift all, [5, 11, 12, 13, 6]
insert at 0
i=4 6 [5, 11, 12, 13] 6 < 13, 12, 11 → shift three, [5, 6, 11, 12, 13] ✓
insert
📊 Complexity:
Time: O(n²) average, O(n) best (already sorted) | Space: O(1) | Stable: Yes
3. Selection Sort
Selection Sort divides the array into a sorted part (left) and an unsorted part (right). In each iteration, it
finds the minimum element from the unsorted part and swaps it with the leftmost element of the
unsorted region. This process repeats until the entire array is sorted.
Key Concepts
• Outer loop selects the position to fill (from 0 to n-2).
• Inner loop scans the remaining unsorted portion to find the minimum.
• After the inner loop, the minimum is swapped into the current position.
• Only one swap per pass — efficient in terms of number of swaps.
C Code
void selectionSort(int arr[], int n){
for(int i=0;i<n-1;i++){
int min=i;
for(int j=i+1;j<n;j++){
if(arr[j]<arr[min]){
min=j;
}
}
int temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
Step-by-Step Example
Input array: [64, 25, 12, 22, 11]
Pass Unsorted Range Minimum Swap Array After
(i) Found
i=0 [64,25,12,22,11] 11 at index 4 Swap arr[0]↔arr[4] [11, 25, 12, 22, 64]
i=1 [25,12,22,64] 12 at index 2 Swap arr[1]↔arr[2] [11, 12, 25, 22, 64]
i=2 [25,22,64] 22 at index 3 Swap arr[2]↔arr[3] [11, 12, 22, 25, 64]
i=3 [25,64] 25 at index 3 No swap needed [11, 12, 22, 25, 64] ✓
📊 Complexity:
Time: O(n²) all cases | Space: O(1) | Stable: No (due to non-adjacent swaps)
4. Quick Sort
Quick Sort is a highly efficient divide-and-conquer algorithm. It selects a 'pivot' element, partitions the
array so elements smaller than the pivot are on its left and larger ones on its right, then recursively
sorts both halves. The pivot ends up in its final sorted position after each partition.
Key Concepts
• Pivot: the last element (arr[high]) in this implementation.
• Partition: rearranges elements so all values < pivot are on the left.
• After partition, the pivot is placed at its correct index (returned as pi).
• quickSort() recursively sorts the sub-arrays on both sides of pi.
C Code
int partition(int arr[], int low, int high){
int pivot=arr[high];
int i=low-1;
for(int j=low;j<high;j++){
if(arr[j]<pivot){
i++;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
int temp=arr[i+1];
arr[i+1]=arr[high];
arr[high]=temp;
return i+1;
}
void quickSort(int arr[], int low, int high){
if(low<high){
int pi=partition(arr,low,high);
quickSort(arr,low,pi-1);
quickSort(arr,pi+1,high);
}
}
Step-by-Step Example
Input array: [10, 7, 8, 9, 1, 5] → Pivot = 5 (arr[high])
Partition Step (pivot = 5):
j arr[j] arr[j] < pivot? i after Array State
0 10 No (10 ≥ 5) i=-1 [10, 7, 8, 9, 1, 5]
1 7 No (7 ≥ 5) i=-1 [10, 7, 8, 9, 1, 5]
2 8 No (8 ≥ 5) i=-1 [10, 7, 8, 9, 1, 5]
3 9 No (9 ≥ 5) i=-1 [10, 7, 8, 9, 1, 5]
4 1 Yes (1 < 5) i=0 [1, 7, 8, 9, 10, 5] (swap i=0,j=4)
- Don Pivot swap: pi=1 [1, 5, 8, 9, 10, 7] ✓
e arr[i+1]↔arr[high]
Now 5 is in its correct position (index 1). Recurse on [1] and [8, 9, 10, 7].
📊 Complexity:
Time: O(n log n) average, O(n²) worst (sorted input) | Space: O(log n) | Stable: No
5. Merge Sort
Merge Sort is a stable, divide-and-conquer algorithm. It recursively splits the array into halves until each
sub-array has one element (trivially sorted), then merges the sorted halves back together in order. The
merge step is where the actual sorting happens.
Key Concepts
• Divide: split the array at the midpoint m = (l+r)/2.
• Conquer: recursively sort the left half [l..m] and right half [m+1..r].
• Merge: combine two sorted halves into one sorted array using a temp buffer.
• Both halves are compared element-by-element; smaller goes into temp first.
C Code
void merge(int arr[], int l, int m, int r){
int i=l, j=m+1, k=0;
int temp[100];
while(i<=m && j<=r){
if(arr[i]<arr[j])
temp[k++]=arr[i++];
else
temp[k++]=arr[j++];
}
while(i<=m) temp[k++]=arr[i++];
while(j<=r) temp[k++]=arr[j++];
for(i=l,k=0;i<=r;i++,k++)
arr[i]=temp[k];
}
void mergeSort(int arr[], int l, int r){
if(l<r){
int m=(l+r)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
}
Step-by-Step Example
Input array: [38, 27, 43, 3]
Division Phase:
Level 0: [38, 27, 43, 3]
Level 1: [38, 27] | [43, 3]
Level 2: [38] [27] | [43] [3] ← base case, single elements
Merge Phase:
Merge Step Left Half Right Half Merge Result
Step 1 [38] [27] Compare 38>27 → [27, 38]
Step 2 [43] [3] Compare 43>3 → [3, 43]
Step 3 [27, 38] [3, 43] 3<27→take 3; 27<43→take 27; 38<43→take
38; take 43 → [3, 27, 38, 43] ✓
📊 Complexity:
Time: O(n log n) always | Space: O(n) for temp array | Stable: Yes
Quick Comparison
Algorithm Best Average Worst Space Stable
Bubble Sort O(n) O(n²) O(n²) O(1) Yes
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(n²) O(1) No
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes