3.13 Insertion Sort

1. Insertion Sort

Split the array into sorted and unsorted parts, take each element from the unsorted part, and insert it into the already sorted part.

When the array is relatively ordered, it is usually more efficient than selection sort; when the array is already ordered, the best-case time complexity is O(N).

2. Characteristics

• Stability: stable
• In-place sorting
• Space complexity: O(1)
• Time complexity: O(n²)

3. Process

4. Implementation

//O(N²)
func InsertionSort(data []model.Comparable) {
	// data[0...i) is sorted; data[i...n) is unsorted
	// After each outer loop, data[i] is placed in the appropriate position
	for i := 0; i < len(data); i++ {
		for j := i; j-1 >= 0; j-- {
			// data[0...i) is sorted; put data[i] in the appropriate position
			if data[j].CompareTo(data[j-1]) < 0 {
				util.Swap(data, j, j-1)
			} else {
				break
			}
		}
	}
}

//O(N²). Reduces the number of swaps compared with the implementation above
func InsertionSort2(data []model.Comparable) {
	// data[0...i) is sorted; data[i...n) is unsorted
	// After each outer loop, data[i] is placed in the appropriate position
	for i := 1; i < len(data); i++ {

        // data[0...i) is sorted; put data[i] in the appropriate position
		toBeInserted := data[i]
		position := i
		for position > 0 && data[position-1].CompareTo(toBeInserted) > 0 {
		    // Reduce the number of swaps
			data[position] = data[position-1]
			position--
		}

		data[position] = toBeInserted
	}
}

4.1. Test

func TestInsertionSort(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	InsertionSort(data)
	fmt.Println(data)
}

5. References

• Sorting Algorithm Stability - Baidu Baike
• 6.9. The Insertion Sort — Problem Solving with Algorithms and Data Structures