<jupyter_start><jupyter_text>SortingLecture by <NAME> at MITVideo link: [https://www.youtube.com/watch?v=Kg4bqzAqRBM&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=3](https://www.youtube.com/watch?v=Kg4bqzAqRBM&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=3)<jupyter_code>import random, time
def generateArray(n: int=10, min_range: int=-100, max_range: int=100) -> list:
    '''
    Helper function to generate an array of size n 
    where elements are in the (min-range, max_range) range
    '''
    array=[random.randint(min_range, max_range) for i in range(n)]
    return array<jupyter_output><empty_output><jupyter_text>Insertion Sort ```For i=1..n The first element is sorted by default   insert A[i] into sorted array A[0:i-1]    pairwise swaps down to the correct position```<jupyter_code>def insertionSort(array: list, ascending: bool= True, verbose: int = 1) -> None:
    '''
    This function sorts the array in-place and does not return anything
    ascending: if True, the array will be returned in ascending order, else in descending order
    verbose: 0 - doesn't show any ouptut. 
             1 - displays array before and after sorting and the number of swaps
             2 - displays every time a swap is made
    '''
    assert verbose in [0,1,2], "Invalid value for verbose"
    if verbose:
        print("Before sorting")
        print(array)
    if ascending:
        mult_factor=1
    else:
        mult_factor=-1
    swap_count=0
    for key_idx in range(1,len(array)):
        for inner_idx in range(key_idx):
            key,el=array[key_idx]*mult_factor, array[inner_idx]*mult_factor
            if key<el:
                array[inner_idx],array[key_idx]=array[key_idx],array[inner_idx]
                swap_count+=1
                if verbose>1:
                    print(f"After swap #{swap_count}", array)
                
    if verbose:
        print(f"After sorting. Total number of swaps: {swap_count}")
        print(array)<jupyter_output><empty_output><jupyter_text>**Improvement to insertion sort**- *Observation*: All elements before the current one are already sorted- *Action*: Use binary search instead of pairwise swaps. **Note**: The number of swaps does not decrease since all elements have to be moved to put the key in the correct position **TO-DO** Implement ascending/descending for binary insertion sort<jupyter_code>def rotateElements(arr,start,end) -> None:
    assert start<len(arr) and end<len(arr) and start<=end, "Cannot move elements"
    for i in range(end, start, -1):
        arr[i],arr[i-1]=arr[i-1],arr[i]
    return
def binarySearch(arr, val, start, end):
    if start==end:
        temp=arr[start]
        if temp>val:
            return start
        else:
            return start+1
    if start>end:
        return start
    mid=(start+end)//2
    temp=array[mid]
    if temp>val:
        return binarySearch(arr, val,start, mid-1)
    elif temp<val:
        return binarySearch(arr, val, mid+1, end)
    else:
        return mid
        
def improvedInsertionSort(array: list, ascending: bool= True, verbose: int = 1) -> None:
    '''
    This function sorts the array in-place and does not return anything
    ascending: if True, the array will be returned in ascending order, else in descending order
    verbose: 0 - doesn't show any ouptut. 
             1 - displays array before and after sorting and the number of swaps
             2 - displays every time a swap is made
    '''
    assert verbose in [0,1,2], "Invalid value for verbose"
    if verbose:
        print("Before sorting")
        print(array)
    swap_count=0
    for key_idx in range(1,len(array)):
        lo, hi= 0, key_idx-1
        key=array[key_idx]
        pos=binarySearch(array,key,lo,hi)
        if pos!=key_idx:
            rotateElements(array, pos, key_idx)
            swap_count+=key_idx-pos
        if verbose>1:
            print(array)          
    if verbose:
        print(f"After sorting. Total number of swaps: {swap_count}")
        print(array)<jupyter_output><empty_output><jupyter_text>Merge Sort ```Break down list into single elements, which by definition are sortedMerge each of these one-element lists into a sorted list```<jupyter_code>def mergeSort(array):
    '''
    Breaks down the list into single-element lists
    '''
    if len(array)>1:
        mid=len(array)//2
        left_arr=array[:mid]
        right_arr=array[mid:]
        mergeSort(left_arr)
        mergeSort(right_arr)
        return merge(left_arr, right_arr, array)

def merge(left_arr, right_arr, array):
    '''
    Takes two sorted lists as input and 
    merges them in O(|left_arr| + |right_arr|) time
    '''
    i,j,k=0,0,0
    while(i<len(left_arr) and j<len(right_arr)):
        if left_arr[i]<right_arr[j]:
            array[k]=left_arr[i]
            i+=1
        else:
            array[k]=right_arr[j]
            j+=1
        k+=1
    while i<len(left_arr):
        array[k]=left_arr[i]
        i+=1
        k+=1
    while j<len(right_arr):
        array[k]=right_arr[j]
        j+=1
        k+=1<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10503540519276161, 'fraction_numerical': 0.015145554681353266, 'mean_word_length': 2.763878608438194, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 28, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '554745', 'license': 'MIT', 'n_tokens_mistral': 1678, 'n_tokens_neox': 1611, 'n_words': 467, 'path': 'Lecture 03/6.006.L3.ipynb', 'repo_name': 'shamikbose/MIT6.006', 'size': '5090'}