Improve the performance of insertion sort

[SteveLauC]

The performance of insertion sort can be enhanced by simply move items back instead of swap them:

pub fn insertion_sort<T>(arr: &mut [T])
where
    T: cmp::PartialOrd + Copy,
{
    for i in 1..arr.len() {
        let cur = arr[i];
        let mut j = i - 1;

        while arr[j] > cur {
            arr[j + 1] = arr[j]; // move items back
            if j == 0 {
                break;
            }
            j -= 1;
        }

        // we exit the loop from that break statement
        if j == 0 && arr[0] > cur {
            arr[0] = cur;
        } else {
            // `arr[j] > cur` is not satsified, exit from condition judgement
            arr[j + 1] = cur;
        }
    }
}

By doing so, we can reduce the number of accesses to array elements by half. To demo this, I wrote a single test:

//! main.rs

mod sort;

use rand::random;
use sort::{insertion_enhanced_version, insertion_orig_version};
use std::{
    env::args,
    process::exit,
    time::{Duration, Instant},
};

fn main() {
    let av: Vec<String> = args().collect();
    if av.len() < 3 {
        eprintln!("usage: {} LEN <ALGORITHM>", av[0]);
        exit(1);
    }

    let len: usize = av[1].parse().unwrap();
    let mut s: Vec<i32> = random_array(len);

    let now: Instant = Instant::now();
    match av[2].as_str() {
        "orig" => insertion_orig_version(&mut s),
        "enhanced" => insertion_enhanced_version(&mut s),
        _ => todo!("not implemented yet"),
    }
    let elapsed: Duration = now.elapsed();

    println!(
        "Use {} to sort {} numbers, consuming {:?}",
        av[2].as_str(),
        av[1].as_str(),
        elapsed
    );
}

fn random_array(len: usize) -> Vec<i32> {
    (0..len).into_iter().map(|_| random()).collect()
}

//! sort.rs

pub fn insertion_enhanced_version<T>(arr: &mut [T])
where
    T: PartialOrd + Copy,
{
    for i in 1..arr.len() {
        let cur = arr[i];
        let mut j = i - 1;

        while arr[j] > cur {
            arr[j + 1] = arr[j];
            if j == 0 {
                break;
            }
            j -= 1;
        }

        // we exit the loop from that break statement
        if j == 0 && arr[0] > cur {
            arr[0] = cur;
        } else {
            // `arr[j] > cur` is not satsified, exit from condition judgement
            arr[j + 1] = cur;
        }
    }
}
pub fn insertion_orig_version<T>(arr: &mut [T])
where
    T: PartialOrd + Copy,
{
    for i in 1..arr.len() {
        let cur = arr[i];
        let mut j = i - 1;

        while arr[j] > cur {
            arr.swap(j + 1, j);
            if j == 0 {
                break;
            }
            j -= 1;
        }
    }
}

You can specify how many items you wanna sort, and choose the algorithm you want, it will give you the time consumed on that:

$ cargo run 10000 orig
Use orig to sort 10000 numbers, consuming 683.218631ms
$ cargo run 10000 enhanced
Use enhanced to sort 10000 numbers, consuming 210.417512ms
$ cargo run 100000 orig
Use orig to sort 100000 numbers, consuming 68.68202042s
$ cargo run 100000 enhanced
Use enhanced to sort 100000 numbers, consuming 20.609979502s

As you can see, we got 3 times better performance:)
And this is the result tested on my machine:

$ neofetch
             /////////////                steve@pop-os
         /////////////////////            ------------
      ///////*767////////////////         OS: Pop!_OS 22.04 LTS x86_64
    //////7676767676*//////////////       Host: MacBookPro12,1 1.0
   /////76767//7676767//////////////      Kernel: 5.18.10-76051810-generic
  /////767676///*76767///////////////     Uptime: 2 days, 21 hours, 16 mins
 ///////767676///76767.///7676*///////    Packages: 2426 (dpkg), 35 (flatpak)
/////////767676//76767///767676////////   Shell: zsh 5.8.1
//////////76767676767////76767/////////   Resolution: 1920x1080
///////////76767676//////7676//////////   DE: GNOME 42.2
////////////,7676,///////767///////////   WM: Mutter
/////////////*7676///////76////////////   WM Theme: Pop
///////////////7676////////////////////   Theme: Pop [GTK2/3]
 ///////////////7676///767////////////    Icons: Pop [GTK2/3]
  //////////////////////'////////////     Terminal: tmux
   //////.7676767676767676767,//////      CPU: Intel i5-5257U (4) @ 3.100GHz
    /////767676767676767676767/////       GPU: Intel Iris Graphics 6100
      ///////////////////////////         Memory: 4352MiB / 7853MiB
         /////////////////////            Disk (/): 50G / 103G (52%)
             /////////////

[SteveLauC]

I made a PR #350 for this issue, if it looks good, we can merge it:)