Insertion sort is a simple sorting algorithm that mimics the way we sort small collections of things in our daily lives. Assume that we are given an array of  elements that are to be sorted. Insertion sort subdivides the array into two parts: A first part containing already sorted elements and the unsorted rest. In every step, insertion sort takes one element  from the unsorted part (it doesn’t matter which one, typically one takes the first).

Then, it inserts at the right spot in the sorted part and moves the remaining sorted elements greater than the inserted element one up.

This step is repeated  times until the unsorted part is empty. Initially, the sorted part consists of just the first element of the array and the rest of the array constitutes the unsorted part.

When counting the number of comparisons, the worst-case running time of insertion sort is  because if the case that the input is already sorted, we need comparisons when inserting the -the element. This sums up to comparisons.

Finally, the following RISC-V code implements insertion sort for integer arrays:

    .text
    # a0 address of first element
    # a1 address of element past the last
insertsort:
    addi   t0, a0, 4
outer_loop:
    beq    t0, a1, outer_end
    mv     t1, t0
inner_loop:
    beq    t1, a0, inner_end
    lw     t2, 0(t1)
    lw     t3, -4(t1)
    blt    t3, t2, inner_end
    sw     t2, -4(t1)
    sw     t3, 0(t1)
    addi   t1, t1, -4
    j      inner_loop
inner_end:
    addi   t0, t0, 4
    j      outer_loop
outer_end:
    ret