<jupyter_start><jupyter_text>Merge Sort  Sorting Algorithms and Their Time Complexity  Bubble SortRuntime: O(n^2) average and worst case. Memory: O(1)Explain: for each position in the list, we compare it with its ajacent (next) item. If the current item is bigger than the next item, we swap them. Thus, at the end of each iteration, the biggest number in the list will be place at the end.<jupyter_code>def bubble_sort_one_iteration(l):
    for i in range(len(l)-1):
        if l[i] > l[i+1]:
            temp = l[i]
            l[i] = l[i+1]
            l[i+1] = temp
    return l<jupyter_output><empty_output><jupyter_text>Explain: we repeat the first iteration for n-1 times for a list of n items. For example, 3 numbers require 2 swaps maximum.<jupyter_code>def bubble_sort(l):
    for j in range(len(l)-1):
        for i in range(len(l)-1):
            if l[i] > l[i+1]:
                temp = l[i]
                l[i] = l[i+1]
                l[i+1] = temp
        print(l)
    return l

print(bubble_sort([4,3,9,8,5]))<jupyter_output>[3, 4, 8, 5, 9]
[3, 4, 5, 8, 9]
[3, 4, 5, 8, 9]
[3, 4, 5, 8, 9]
[3, 4, 5, 8, 9]<jupyter_text>Insertion SortRuntime: still O(n) but faster than bubble Sort. The wrost case will be O(n*n)If we imagine a square. Bubble sort will fill in n x n/2 space out of n*n space. Insertion Sort will only need n x n/4 space because insertion sort doesn't need to go through the rest of the list after it found the right spot. In terms of memory, it does the swaping in place<jupyter_code>def insertion_sort(unsorted_list):
    for idx in range(1, len(unsorted_list)):
        search_index = idx
        insert_value = unsorted_list[idx]

        while search_index > 0 and unsorted_list[search_index-1] > insert_value:
            unsorted_list[search_index] = unsorted_list[search_index-1]
            search_index -= 1
        unsorted_list[search_index] = insert_value<jupyter_output><empty_output><jupyter_text>Quick SortRuntime: On average, it should be Nlog(N).We will divide the list to log(N) level deep and in each level, we have N elements to sort. However, in a wrost case situation, in which we picked the largest number every time as the pivot to compare with, we will end up with N.N run time.Big picture:It uses divide and conquer. We select a compare point and call it pivot. Then we split the list to 2 by puting the ones smaller than pivot to the left and the ones bigger to the right. We continue to divide the list until there's only 1 element left.Steps:1. select a pivot (benchmark value)2. have left and right points. Moving from left to right, left pointer is looking for the first value that is bigger than pivot. Right pointer is looking for the first value that is smaller than pivot.3. sawp the two values.4. repeat this process until both pointers cross each other.5. If the pointers crossed each other, then stop and swap the pivot with the right element. Now, all the elements smaller than the pivot is on its left and the bigger on its right6. Repeat this step with left of pivot and right of pivot seperately.<jupyter_code># recursive implementation
def partition(arr,low,high): 
    i = ( low-1 )         # index of smaller element 
    pivot = arr[high]     # pivot 
  
    for j in range(low , high): 
  
        # If current element is smaller than the pivot 
        if   arr[j] < pivot: 
          
            # increment index of smaller element 
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 
  
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 
    
def quickSort(arr, low, high): 
    if low < high: 
  
        # pi is partitioning index, arr[p] is now 
        # at right place 
        pi = partition(arr, low, high) 
  
        # Separately sort elements before 
        # partition and after partition 
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi + 1, high) 
def quicksort(l, start, end):
    if start >= end:
        return
    pivot_idx = 0
    pivot_element = list[pivot_idx]
    
    less_than_pointer = start
    for i in range(start, end):
        if l[i] < pivot_element:
            l[i], l[less_than_pointer] = l[less_than_pointer], l[end]
            less_than_pointer += 1
    l[end], l[less_than_pointer] = l[less_than_pointer], l[end]
    
    quicksort(l, start, less_than_pointer-1)
    quicksort(l, less_than_pointer+1, end)<jupyter_output><empty_output><jupyter_text>Merge Sort<jupyter_code>def merge(left, right):
    result = []

    while (left and right):
        if left [0] < right[0]:
            result.append(left[0])
            left.pop(0)
        else:
            result.append(right[0])
            right.pop(0)
    if left:
        result += left
    if right:
        result += right

    return result



def merge_sort(items):
    if len(items) <= 1:
        return items
    middle_index = len(items) // 2
    left_split = items[:middle_index]
    right_split = items[middle_index:]

    #continue to split them into the smallest unit
    left_sorted = merge_sort(left_split)
    right_sorted = merge_sort(right_split)

    return merge(left_sorted, right_sorted)
# implementation using linked list

class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
class LinkedList: 
    def __init__(self): 
        self.head = None
      
    # push new value to linked list 
    # using append method 
    def append(self, new_value): 
          
        # Allocate new node 
        new_node = Node(new_value) 
          
        # if head is None, initialize it to new node 
        if self.head is None: 
            self.head = new_node 
            return
        curr_node = self.head 
        while curr_node.next is not None: 
            curr_node = curr_node.next
              
        # Append the new node at the end 
        # of the linked list 
        curr_node.next = new_node 
          
    def sortedMerge(self, a, b): 
        result = None
          
        # Base cases 
        if a == None: 
            return b 
        if b == None: 
            return a 
              
        # pick either a or b and recur.. 
        if a.data <= b.data: 
            result = a 
            result.next = self.sortedMerge(a.next, b) 
        else: 
            result = b 
            result.next = self.sortedMerge(a, b.next) 
        return result 
      
    def mergeSort(self, h): 
          
        # Base case if head is None 
        if h == None or h.next == None: 
            return h 
  
        # get the middle of the list  
        middle = self.getMiddle(h) 
        nexttomiddle = middle.next
  
        # set the next of middle node to None 
        middle.next = None
  
        # Apply mergeSort on left list  
        left = self.mergeSort(h) 
          
        # Apply mergeSort on right list 
        right = self.mergeSort(nexttomiddle) 
  
        # Merge the left and right lists  
        sortedlist = self.sortedMerge(left, right) 
        return sortedlist 
      
    # Utility function to get the middle  
    # of the linked list  
    def getMiddle(self, head): 
        if (head == None): 
            return head 
  
        slow = head 
        fast = head 
  
        while (fast.next != None and 
               fast.next.next != None): 
            slow = slow.next
            fast = fast.next.next
              
        return slow 
          
# Utility function to print the linked list  
def printList(head): 
    if head is None: 
        print(' ') 
        return
    curr_node = head 
    while curr_node: 
        print(curr_node.data, end = " ") 
        curr_node = curr_node.next
    print(' ')<jupyter_output><empty_output><jupyter_text>Merge Sort vs. Quick Sort - which one to pick?Merge sort is very stable. The wrost case situation for Merge Sort is O(n(logn)) while quick sort can be n.n. On the other hand, quick sort can also be much faster than merge sort when you picked a good pivot.However, Quick Sort only requires O(n(logn)) memories - the pivot while Merge sort requires O(n)The rule of thumb is to use quick sort for smaller array while using merge sort for larger array. - why prefer array for quick sort while use linked list for merge sort?Both sorting algorithms can be implemented by using either array or linked list. However, it's better to use array for quick sort because quick sort does not require additional memory but requires lots of random access to elements. Referecing elements in array s O(1) while in linked list is O(N). For merge sort, it is vice versa.Merge sort also requries insert while quick sort is in-place sort. Linked list is much better or insertion.   TimSort: This is the default sorting for Java and PythonRuntime:  O(nLogn), even in the wrost caseBig picture:sort the small pices using insertion sort, then merges the pices using merge sort. Modified from the previous insertion sort, now we added in left and right index. So that we can only sort part of the string. For the merging part, it remains the same.<jupyter_code>def insertion_sort(array, left=0, right=None):
    if right is None:
        right = len(array) - 1
    for i in range(left + 1, right + 1):
        key_item = array[i]

        j = i - 1
        while j >= left and array[j] > key_item:
            array[j + 1] = array[j]
            j -= 1
        
        array[j + 1] = key_item

    return array
def timsort(array):
    min_run = 32
    n = len(array)

    for i in range(0, n, min_run):
        insertion_sort(array, i, min((i + min_run - 1), n - 1))
    
    #now we start merging
    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            # midpoint is where the first array ends
            # and the second one starts.
            # the end is where the 2nd array ends.
            midpoint = start + size - 1
            end = min((start + size * 2 - 1), (n - 1))

            merged_array = merge(left=array[start:midpoint + 1], right=array[midpoint + 1:end + 1])
            #put the merged part back to the array (this also shows merge_sort costs more memory space)
            array[start:start + len(merged_array)] = merged_array
        size *= 2
    return array<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07909383849233473, 'fraction_numerical': 0.01005761156137096, 'mean_word_length': 2.2483349191246433, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '531033', 'license': 'MIT', 'n_tokens_mistral': 3181, 'n_tokens_neox': 2993, 'n_words': 1209, 'path': 'algo_imple/sorting.ipynb', 'repo_name': 'linnndachen/data-structure-and-algorithms', 'size': '10241'}