Sorting Algorithms in Java: Bubble, Selection, Insertion, Merge, and Quick Sort

Chapter 3: Insertion Sort in Java

1. Description of Insertion Sort (No Coding)

Insertion Sort is an efficient sorting algorithm, especially for small or nearly sorted datasets. It works similarly to how we sort playing cards in our hands: we pick a card and insert it into the correct position among the already sorted cards.

Working Principle of Insertion Sort

1. Start from the second element (assuming the first element is already sorted).
2. Compare it with elements before it and shift the larger elements to the right.
3. Insert the picked element into its correct position.
4. Repeat the process for all remaining elements.

Unlike Bubble Sort and Selection Sort, Insertion Sort is adaptive – it reduces the number of comparisons if the array is nearly sorted.

Visualization Example

Unsorted Array:

[5, 3, 8, 4, 2]

Pass 1 (Insert 3 in sorted position):

• Compare 3 with 5, shift 5 right.
• Insert 3 before 5.
• Array after insertion: [3, 5, 8, 4, 2]

Pass 2 (Insert 8 in sorted position):

• No changes needed as 8 is already in the correct place.

Pass 3 (Insert 4 in sorted position):

• Compare 4 with 8, shift 8 right.
• Compare 4 with 5, shift 5 right.
• Insert 4 in its correct position.
• Array after insertion: [3, 4, 5, 8, 2]

Pass 4 (Insert 2 in sorted position):

• Compare 2 with 8, shift 8 right.
• Compare 2 with 5, shift 5 right.
• Compare 2 with 4, shift 4 right.
• Compare 2 with 3, shift 3 right.
• Insert 2 in its correct position.
• Final sorted array: [2, 3, 4, 5, 8]

2. Insertion Sort Coding Examples

(a) Syllabus-Based Example (Sorting an array of numbers)

public class InsertionSortExample {

    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;

        }

    }

    public static void main(String args[]) {

        int arr[] = {5, 3, 8, 4, 2};

        insertionSort(arr);

        System.out.println(java.util.Arrays.toString(arr));

    }

}

Output:
[2, 3, 4, 5, 8]

(b) Real-World Example (Sorting student exam scores in ascending order)

public class InsertionSortScores {

    static void insertionSort(double scores[]) {

        int n = scores.length;

        for (int i = 1; i < n; i++) {

            double key = scores[i];

            int j = i - 1;

            while (j >= 0 && scores[j] > key) {

                scores[j + 1] = scores[j];

                j--;

            }

            scores[j + 1] = key;

        }

    }

    public static void main(String args[]) {

        double scores[] = {85.5, 92.0, 76.8, 89.3, 94.5};

        insertionSort(scores);

        System.out.println(java.util.Arrays.toString(scores));

    }

}

Output:
[76.8, 85.5, 89.3, 92.0, 94.5]

3. Advantages of Insertion Sort (Pros)

✔ Efficient for small datasets – Faster than Bubble Sort and Selection Sort for n < 50.
✔ Adaptive sorting – It performs well when the array is already or nearly sorted (O(n)).
✔ Stable sorting algorithm – Maintains the relative order of duplicate elements.
✔ In-place sorting – Requires no extra memory (O(1) space complexity).
✔ Used in hybrid sorting algorithms – Some efficient sorting techniques like Tim Sort use Insertion Sort for small partitions.

4. Disadvantages of Insertion Sort (Cons)

❌ Inefficient for large datasets – Time complexity is O(n²) in the worst case.
❌ Comparisons increase with unsorted input – Requires O(n²) comparisons for reversed arrays.
❌ Slower than Quick Sort and Merge Sort – Not suitable for large-scale applications.
❌ Does not work well for large datasets – Performance degrades as n increases.
❌ More shifting operations – Every insertion shifts elements to the right, increasing overhead.

5. How is Insertion Sort Better Than Other Sorting Techniques?

• More efficient than Bubble Sort and Selection Sort for nearly sorted data (O(n)).
• Stable sorting technique – Unlike Selection Sort, it maintains the order of equal elements.
• Less number of swaps compared to Bubble Sort – Shifting is used instead of swapping.
• Faster for small datasets – It is better than Merge Sort and Quick Sort for n < 50.
• Used inside efficient sorting algorithms – Hybrid sorting algorithms like Tim Sort and Intro Sort use Insertion Sort for sorting small data chunks.

6. Best Cases to Use Insertion Sort

✔ When the dataset is nearly sorted – Performs in O(n) time complexity.
✔ When stability is required – Maintains order of duplicate values.
✔ For sorting small datasets – Works well when n < 50.
✔ For online sorting – Useful when new elements need to be inserted dynamically.
✔ As a helper in hybrid sorting algorithms – Used in Tim Sort and Shell Sort.

7. Worst Cases to Use Insertion Sort

❌ For large datasets (n > 1000) – Merge Sort or Quick Sort is better.
❌ When the dataset is reversed – Requires O(n²) swaps and O(n²) comparisons.
❌ For parallel processing – Not efficient for distributed sorting.
❌ When minimal time complexity is needed – Other algorithms like Merge Sort (O(n log n)) are faster.
❌ When a sorting algorithm must be efficient in all cases – Quick Sort is better as it works well on all types of datasets.