What is Insertion Sort
Insertion Sort is a simple sorting algorithm that works by iterating through an array from left to right and "inserting" each element in its correct position among the already sorted elements. In other words, it starts by considering the first element to be sorted and then compares the second element to it, moving it to the left if it is smaller or leaving it in place if it is larger. It then repeats this process for the third element, the fourth element, and so on until the entire array is sorted.
Who invented it?
Insertion Sort has been around for a long time and it's not clear who exactly invented it. However, it is known to have been used by the ancient Greeks for sorting data in lists and tables.
Pseudocode
// C++ code snippet
for i = 1 to n-1
j = i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j = j - 1
In this pseudocode, A is the array to be sorted and n is its length. The outer for loop iterates through each element of the array except for the first one, which is already considered to be sorted. The inner while loop compares the current element with the one immediately to its left and swaps them if they are out of order. The loop continues until the current element is in its correct position among the sorted elements to its left.
Sample Code
// C++ code snippet
vector insertion_sort(vector& A) {
for (int i = 1; i < A.size(); i++) {
int j = i;
while (j > 0 && A[j-1] > A[j]) {
swap(A[j], A[j-1]);
j--;
}
}
return A;
}
int main() {
vector A = {5, 2, 4, 6, 1, 3};
vector sorted_A = insertion_sort(A);
for (int i = 0; i < sorted_A.size(); i++) {
cout << sorted_A[i] << " ";
}
cout << endl;
return 0;
}
# Python code snippet
def insertion_sort(A):
for i in range(1, len(A)):
j = i
while j > 0 and A[j-1] > A[j]:
A[j], A[j-1] = A[j-1], A[j]
j -= 1
return A
# Example usage
A = [5, 2, 4, 6, 1, 3]
sorted_A = insertion_sort(A)
print(sorted_A)
import java.util.Arrays;
public class InsertionSort {
public static int[] insertion_sort(int[] A) {
for (int i = 1; i < A.length; i++) {
int j = i;
while (j > 0 && A[j-1] > A[j]) {
int temp = A[j];
A[j] = A[j-1];
A[j-1] = temp;
j--;
}
}
return A;
}
public static void main(String[] args) {
int[] A = {5, 2, 4, 6, 1, 3};
int[] sorted_A = insertion_sort(A);
System.out.println(Arrays.toString(sorted_A));
}
}
Time and Space Complexity
The time complexity of Insertion Sort is O(n^2) in the worst case, where n is the length of the array. This occurs when the array is already sorted in reverse order, because each element must be compared with every element to its left before it can be inserted in its correct position.
The space complexity of Insertion Sort is O(1) because it only uses a constant amount of additional space to store temporary variables for swapping elements.
Advantages
- Simple and easy to implement.
- Works well for small arrays or partially sorted arrays.
- Requires very little additional memory.
Disadvantages
- Slow for large arrays or arrays that are mostly unsorted.
- Performs poorly in terms of time complexity compared to more advanced sorting algorithms such as Merge Sort and Quick Sort.