Sorting algorithm refreshers........Insertion Sort!

Here is the 3rd and final of the "crappy" sorting algorithms. It too performs at the O(n^2) growth rate. This algorithm is better than the previous 2 however since it is designed for inserting. This means that the algorithm assumes part of the array is sorted so therefore less swaps.

1. Start with a outer loop that starts ONE index above the very first element and counts till the end of the array
2. Store the contents of the array at the outer loops index
3. Inside have another loop that is responsible for shifting all the values less than/greater than the value in array pointed to by the outer loops index
4. Once everything has been shifted place the value from step 2 into the newly created space from step 3

#include

int main(void) {
    
    int list[] = { 3, 4, 1, 10, 23, 40, 2, 9};
    
    int arr_length = sizeof(list)/sizeof(list[0]);
    
    for(int i = 1; i < arr_length; ++i){        
        
        int curr = list[i];
        int curr_i = i;
        
        while(curr_i > 0 && list[curr_i-1] > curr ) {
            
            list[curr_i] = list[curr_i -1];
            curr_i--;
        } 
        
        list[curr_i] = curr;
               
    }
    
    for( int i = 0; i < arr_length; ++i) {
        printf("%d ", list[i]);
    }
    
    printf("\n");
    
}