Insertion Sort

Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. The algorithm works by dividing the array into a sorted and an unsorted part. Initially, the sorted part contains only the first element, and the unsorted part contains the rest of the elements. It then takes elements from the unsorted part one by one and inserts them into the correct position in the sorted part.


Algorithm:

Bubble Sort Visualization
Complexity
Best Time Complexity O(n)
Average Time Complexity O(n2)
Worst Time Complexity O(n2)
Space Complexity O(1)

Insertion Sort Visualizer

Insertion Sort Code

public static void insertionSort(int[] arr) {
                        for (int i = 1; i < arr.length; i++) {
                            int key = arr[i];
                            int j = i - 1;
                
                            while (j >= 0 && arr[j] > key) {
                                arr[j + 1] = arr[j];
                                j = j - 1;
                            }
                            arr[j + 1] = key;
                        }
                    }
                
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 = j - 1;
                            }
                            arr[j + 1] = key;
                        }
                    }
                    
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 = j - 1;
                            }
                            arr[j + 1] = key;
                        }
                    }
def insertion_sort(arr):
                        for i in range(1, len(arr)):
                            key = arr[i]
                            j = i - 1
                    
                            while j >= 0 and arr[j] > key:
                                arr[j + 1] = arr[j]
                                j -= 1
                            arr[j + 1] = key

Practice Questions

Question Number Question Title Level Link
1 Sort an Array Easy Link
2 Sort List Medium Link
3 Insertion Sort List Hard Link