Insertion Sort

Insertion sort

1. This image is a good analogy.
2. The cards in the hand are the sorted set.
3. The cards dealt for the player that are still on the table are the unsorted set.

Assuming that the entire array is divided into sorted and unsorted parts, each of the elements from the unsorted part is inserted into the correct position in the sorted part. Hence the name, Insertion sort.

Concept: Builds a sorted array one element at a time by inserting elements into their correct positions within the sorted portion of the array.

It has a time complexity of O(n^2), thus being slower than heapsort, merge sort and also shellsort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence.

Idea

1. Let a[0], …, a[n-1] be the sequence to be sorted.
2. At the beginning and after each iteration of the algorithm the sequence consists of two parts:
   1. the first part a[0], …, a[i-1] is already sorted,
   2. the second part a[i], …, a[n-1] is still unsorted (i element 0, …, n).
3. In order to insert element a[i] into the sorted part, it is compared with a[i-1], a[i-2] etc.
4. When an element a[j] with a[j] less or equal a[i] is found, a[i] is inserted behind it.
5. If no such element is found, then a[i] is inserted at the beginning of the sequence.
6. After inserting element a[i], the length of the sorted part has increased by one.
7. In the next iteration, a[i+1] is inserted into the sorted part etc.
8. While at the beginning, the sorted part consists of element a[0] only, at the end it consists of all elements a[0], …, a[n-1].

Example

Let’s sort the array [5, 2, 4, 6, 1, 3] using insertion sort.

Step-by-Step Walkthrough:

1. Initial array: [5, 2, 4, 6, 1, 3]
   1. First element (5) is considered sorted.

1. i = 1, key = 2:
   1. Compare 2 with 5 (at j = 0). Since 5 > 2, shift 5 to A[1].
   2. Insert 2 at A[0].
   3. Array: [2, 5, 4, 6, 1, 3]

1. i = 2, key = 4:

   1. Compare 4 with 5 (at j = 1). Since 5 > 4, shift 5 to A[2].
   2. Compare 4 with 2 (at j = 0). Since 2 < 4, stop.
   3. Insert 4 at A[1].
   4. Array: [2, 4, 5, 6, 1, 3]

2. i = 3, key = 6:

   1. Compare 6 with 5 (at j = 2). Since 5 < 6, stop.
   2. Insert 6 at A[3].
   3. Array: [2, 4, 5, 6, 1, 3]

3. i = 4, key = 1:

   1. Compare 1 with 6 (at j = 3). Since 6 > 1, shift 6 to A[4].
   2. Compare 1 with 5 (at j = 2). Since 5 > 1, shift 5 to A[3].
   3. Compare 1 with 4 (at j = 1). Since 4 > 1, shift 4 to A[2].
   4. Compare 1 with 2 (at j = 0). Since 2 > 1, shift 2 to A[1].
   5. Insert 1 at A[0].
   6. Array: [1, 2, 4, 5, 6, 3]

4. i = 5, key = 3:

   1. Compare 3 with 6 (at j = 4). Since 6 > 3, shift 6 to A[5].
   2. Compare 3 with 5 (at j = 3). Since 5 > 3, shift 5 to A[4].
   3. Compare 3 with 4 (at j = 2). Since 4 > 3, shift 4 to A[3].
   4. Compare 3 with 2 (at j = 1). Since 2 < 3, stop.
   5. Insert 3 at A[2].
   6. Array: [1, 2, 3, 4, 5, 6]

5. Final Sorted Array: [1, 2, 3, 4, 5, 6]

https://github.com/explorer436/programming-playground/tree/main/java-playground/my-implementations/searching-and-sorting/src/main/java/com/my/company/sorting/algorithms

Complexity analysis

1. Time Complexity: O(n²) in worst and average cases, O(n) in best case (nearly sorted array).
2. Space Complexity: O(1) (in-place sorting).
3. Use Case: Efficient for small or nearly sorted arrays, adaptive, and stable.