Sorting algorithms: Insertion sort

Insertion Sort is a simple comparison-based sorting algorithm that builds a sorted array (or list) one element at a time.

It's much like how you might sort playing cards in your hands. You start with an empty left hand and take the cards one by one from a pile. Each card is inserted into the correct position relative to the other cards in your hand (already sorted).

How it Works:

1. Start from the second element (index 1) and compare it to the first element.

2. If the second element is smaller than the first, swap them.

3. Move to the next element (index 2) and compare it to the elements on its left. Shift the elements greater than this element to the right.

4. Insert this element in its correct position.

5. Repeat the process until the array is sorted.

•    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;
  
                // Move elements that are greater than 'key' one position ahead
                while (j >= 0 && arr[j] > key) {
                    arr[j + 1] = arr[j];
                    j = j - 1;
                }
                arr[j + 1] = key;
            }
        }
  

Complexity

Time Complexity:

• Best Case (Already sorted array): O(n) – The algorithm just traverses the list without making any swaps.

• Worst Case (Array sorted in reverse order): O(n²) – Every insertion involves shifting all previous elements.

• Average Case: O(n²) – On average, half the elements will need to be shifted for each insertion.

Space Complexity:

• Space Complexity: O(1) – In-place sorting, so no extra space is needed aside from a few temporary variables.

When to Use Insertion Sort:

• It's efficient for small datasets.

• It's adaptive, meaning it becomes more efficient as the dataset becomes more sorted.

• It's stable (preserves the relative order of elements with equal keys).

• It’s great for sorting nearly sorted data.