Insertion Sort
Insertion sort builds the sorted array one element at a time. It takes each element and inserts it into its correct position among the previously sorted elements. It's efficient for small datasets and nearly sorted data. Time: O(n²) worst, O(n) best. Stable, in-place.
Java implementation:
public static void insertionSort(int[] arr) {
int n = arr.length;
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;
}
}
Two Minute Drill
- Insertion sort inserts each element into sorted part.
- Worst O(n²), best O(n) (nearly sorted).
- Stable, in-place.
- Good for small arrays and online sorting (data arrives gradually).
Need more clarification?
Drop us an email at career@quipoinfotech.com