Insertion Sort Recursion and Iteration in Rust

This post is about the sorting algorithm called Insertion Sort using recursion and iteration in Rust. It is simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Sort Using Recursion

Our codes have 2 functions. The first function only runs a recursive function.

// Call this from some main function
fn insertion_sort_recursive(param_int_array:&mut [i32]) {
    // We need to specify the first index
    insertion_sort_recursive_process(param_int_array, 1);
}

// Call this from some main function

fn insertion_sort_recursive(param_int_array:&mut [i32]) {

// We need to specify the first index

insertion_sort_recursive_process(param_int_array, 1);

}

The second function is the actual Insertion Sort function that uses recursion. It will call itself a number of times until the index + 1 is equals to or grater than the array length.

fn insertion_sort_recursive_process(param_int_array:&mut [i32], index: usize) {
    let value = param_int_array[index];
    let mut  j = index;

    while j > 0 && param_int_array[j - 1] > value {
        param_int_array[j] = param_int_array[j - 1];
        j-=1;
    }

    param_int_array[j] = value;

    if index + 1 < param_int_array.len() {
        insertion_sort_recursive_process(param_int_array, index + 1)
    }
}

fn insertion_sort_recursive_process(param_int_array:&mut [i32], index: usize) {

let value = param_int_array[index];

let mut j = index;

while j > 0 && param_int_array[j - 1] > value {

param_int_array[j] = param_int_array[j - 1];

j-=1;

}

param_int_array[j] = value;

if index + 1 < param_int_array.len() {

insertion_sort_recursive_process(param_int_array, index + 1)

}

Below is an example of codes that use our bootstrap function.

fn main() {
    let mut int_values_array = [1, 0, 9, 4, 8, 177, 8, 5, 6,7 , 4, 3, 2, 1];
    insertion_sort_recursive(&mut int_values_array);
    println!("{:?}", int_values_array);
}

fn main() {

let mut int_values_array = [1, 0, 9, 4, 8, 177, 8, 5, 6,7 , 4, 3, 2, 1];

insertion_sort_recursive(&mut int_values_array);

println!("{:?}", int_values_array);

}

The codes output the following.

[0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 177]

1	[0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 177]

Sort Using Iteration

For this example, we have a function that accepts a mutable reference to an array of i32’s with any length and returns nothing. This is the only function of the Insertion Sort using iteration. Notice that it only relies on a loop and does not call itself a number of times until an condition is met.

fn insertion_sort_iterative(param_int_array:&mut [i32]) {

    // We start off at the second index
    let mut i = 1;

    // Get the length to the array
    let array_len = param_int_array.len();

    // Loop until we reach the length value of the array
    while i <  array_len {

        let value = param_int_array[i];
        let mut j = i;

        // Compare the two values and perform swap if needed
        while j > 0 && param_int_array[j - 1] > value {
            param_int_array[j] = param_int_array[j - 1];
            j-=1;
        }

        param_int_array[j] = value;
        i+=1;
    }
}

fn insertion_sort_iterative(param_int_array:&mut [i32]) {

// We start off at the second index

let mut i = 1;

// Get the length to the array

let array_len = param_int_array.len();

// Loop until we reach the length value of the array

while i < array_len {

let value = param_int_array[i];

let mut j = i;

// Compare the two values and perform swap if needed

while j > 0 && param_int_array[j - 1] > value {

param_int_array[j] = param_int_array[j - 1];

j-=1;

}

param_int_array[j] = value;

i+=1;

}

A sample usage would be:

fn main() {
    let mut int_values_array:[i32; 11] = [1, 0, 9, 8, 5, 6,7 , 4, 3, 2, 1];
    insertion_sort_iterative(&mut int_values_array);
    println!("{:?}", int_values_array);
}

fn main() {