Insertion Sort Algorithm in Rust

1. Introduction

Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It works similarly to how many people sort playing cards in their hands. The algorithm divides the list into a sorted and an unsorted part. Starting from the second element, it picks one element at a time and places it in its correct position in the sorted part by moving the larger values to one position ahead of their current position.

2. Implementation Steps

1. Start from the second element (consider the first element as sorted).

2. Compare the current element with the previous element.

3. If the current element is smaller than the previous element, compare it with elements before the previous element. Continue this process until a larger element or the start of the array is found.

4. Insert the current element in the correct position so that the elements before it are smaller and the elements after it are larger.

5. Repeat the process for each element in the array.

3. Implementation in Rust Programming

fn insertion_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        // While j is not the first element and it's smaller than its predecessor
        while j > 0 && arr[j] < arr[j - 1] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}
fn main() {
    let mut numbers = [8, 2, 4, 9, 3, 6];
    insertion_sort(&mut numbers);
    println!("{:?}", numbers); // Prints: [2, 3, 4, 6, 8, 9]
}

Output:

[2, 3, 4, 6, 8, 9]

Explanation:

1. We define the insertion_sort function which can operate on slices of data that can be ordered (Ord).

2. The algorithm starts from the second element and assumes the first element is sorted.

3. For every element i, it compares this element with its preceding elements.

4. If this element (arr[j]) is smaller than its predecessor (arr[j-1]), we swap them. This process continues as long as j isn't the first element and arr[j] is smaller than arr[j-1].

5. This ensures that after each iteration of the outer loop, the first i+1 elements in the array are sorted.

6. The process repeats until all elements in the array are sorted.