Yossarian0916

from collections import defaultdict


class PriorityQueue:
    """
    each heap element is in form (key value, object handle), while heap
    operations works based on comparing key value and object handle points to
    the corresponding application object.
    """

Yossarian0916

def merge_sort(array):
    if len(array) == 1:
        return array
    else:
        mid = len(array) // 2
        left = merge_sort(array[:mid])
        right = merge_sort(array[mid:])
    return merge(left, right)

Yossarian0916

import random


def partition(array, l, r):
    pivot = array[l]  # choose the 1st element as the pivot
    i = l+1
    for j in range(l+1, r):
        if array[j] < pivot:
            array[j], array[i] = array[i], array[j]
            i += 1

Yossarian0916

"""
compute the number of inversions of the given array
running time is O(nlogn)
using divide and conquer
"""

def count_split_inv(array, left, right):
    count = 0
    i, j = 0, 0
    length = len(left) + len(right)

Yossarian0916

"""
how many girls should one date before he can be in a relationship with 
all 12 zodiac signs
"""
import random


def simulation():
    count = 0
    gf = set()

Yossarian0916

from math import floor, ceil
"""
implement Karatsuba algorithm O(n ** log3)
"""


# karatsuba multiplication
def karatsuba(a, b, base=10):
    """
    divide each number into two halves, the high bits H and the low bits L