<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Insertion Sort (Insert Sort)
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
Complexity
Time
Worst-case
Step1:  work
Step2:  Code2 - ChartTracer
Step3:  work
<ASSISTANT_TASK:>
Python Code:
def insertion_sort(unsorted_list):
    x = ipytracer.List1DTracer(unsorted_list)
    display(x)
    for i in range(1, len(x)):
        j = i - 1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1]  = x[j]
            j = j - 1
        x[j+1] = key
    return x.data
Explanation: Insertion Sort (Insert Sort)
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
Complexity
Time
Worst-case: $O(n^2)$
Bast-case: $O(n)$
Average: $O(n^2)$
Reference
Wikipedea
Code1 - List1DTracer
End of explanation
insertion_sort([6,4,7,9,3,5,1,8,2])
Explanation: work
End of explanation
def insertion_sort(unsorted_list):
    x = ipytracer.ChartTracer(unsorted_list)
    display(x)
    for i in range(1, len(x)):
        j = i - 1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1]  = x[j]
            j = j - 1
        x[j+1] = key
    return x.data
Explanation: Code2 - ChartTracer
End of explanation
insertion_sort([6,4,7,9,3,5,1,8,2])
Explanation: work
End of explanation
<END_TASK>