<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Sorting Algorithms and Complexity
Dr. Chris Gwilliams
gwilliamsc@cardiff.ac.uk
Overview
We have covered
Step1:  Mergesort
Merge sort is a sorting algorithm that works by splitting an array into subarrays, sorting the individual sub arrays and joining it back up into a single, sorted array.
This is known as a divide and conquer algorithm.
Step2:  sorted()
Understandably, we do not write our own sorting implementations each time we need to sort some data.
Step3:  Python has sorting methods built into its standard library.
And it is pretty good!
<ASSISTANT_TASK:>
Python Code:
def ins_sort(k):
    for i in range(1,len(k)):             #since we want to swap an item with previous one, we start from 1
        j = i                             #because we need 2 indexes as one will reduce and we do not want to affect i
        while j > 0 and k[j] < k[j-1]:    #j>0 since there is no value to the left of the 0 index
            k[j], k[j-1] = k[j-1], k[j]   # swap the items, if right one is smaller. (sometimes we use a temp variable)
            j=j-1                         #reduce j and repeat
    return k
print(ins_sort([5,8,1,3,6,9]))
Explanation: Sorting Algorithms and Complexity
Dr. Chris Gwilliams
gwilliamsc@cardiff.ac.uk
Overview
We have covered:
* Iteration
* Recursion
* Functions 
* Sorting Algorithms 
    * Bubble Sort
    * Insertion Sort
Insertion Sort
Start at the second element and loop until the final
Compare index with value before, move it if it is greater
If j is greater than the first index, keep going until we hit the first index
Move i along and repeat 1-3
Example
End of explanation
C = []
A = [1, 3]
B = [2, 4]
C.append(min(min(A), min(B)))
print(C)
A = [3]
B = [2, 4]
C.append(min(min(A), min(B)))
print(C)
A = [3]
B = [4]
C.append(min(min(A), min(B)))
print(C)
# nothing left in A, so just add what is left of B
C += B
print(C)
def merge_sort(x):
    result = []
    if len(x) < 2:
        return x
    mid = int(len(x)/2) # calculate mid point
    y = merge_sort(x[:mid]) #split up to mid point and sort
    z = merge_sort(x[mid:]) #get the rest of the mid point and sort
    i = 0
    j = 0
    while i < len(y) and j < len(z): # loop through both lists
            if y[i] > z[j]: #if left is more than right, add to result and increment index
                result.append(z[j])
                j += 1
            else: #if right is more than left, add to result and increment right index
                result.append(y[i])
                i += 1
    result += y[i:] #we can assume this is sorted, so we add the rest of the lists based on the index
    result += z[j:]
    return result
print(merge_sort([5,8,1,3,6,9]))
Explanation: Mergesort
Merge sort is a sorting algorithm that works by splitting an array into subarrays, sorting the individual sub arrays and joining it back up into a single, sorted array.
This is known as a divide and conquer algorithm.
End of explanation
print(sorted([5, 100, 7, 2, 8149, 23, 19, 473])) 
Explanation: sorted()
Understandably, we do not write our own sorting implementations each time we need to sort some data.
End of explanation
import time
import random
small_sorted_list = [x for x in range(4)]
rev_small_sorted_list = small_sorted_list[::-1]
sorted_list = [x for x in range(1024)]
rev_sorted_list = sorted_list[::-1]
#Start timing
def time_to_sort(to_sort, print_string):
    start = time.time()
    to_sort.sort()
    elapsed = time.time() - start
    print(print_string.format(elapsed))
    
time_to_sort(small_sorted_list, "Sorted: {}")
time_to_sort(rev_small_sorted_list, "Reverse: {}")
time_to_sort([1,5,2,8,3], "Partially Sorted: {}")
time_to_sort([random.randint(0,1000) for r in range(1024)], "Random: {}")
Explanation: Python has sorting methods built into its standard library.
And it is pretty good!
End of explanation
<END_TASK>