Various sorting algorithms including Merge Sort, Counting Sort, and Radix Sort

SortingAlgorithms.py

#################################################################################################################
#   Sorting Algorithms
#   Various sorting algorithms including
#   • Merge Sort        O(nlogn)
#   • Counting Sort     O(n+k) with k being value of largest element
#   • Radix Sort        O(d*[n+k])  with d being number of digits
#
#
#################################################################################################################
def merge(seq1, seq2):
    temp = []
    size = min(len(seq1), len(seq2))

    #Append smallest element of each list in order to output 
    while len(seq1) != 0 and len(seq2) != 0:
        x1, x2 = min(seq1), min(seq2)
        
        if x1 <= x2:
            temp.append(x1)
            seq1.remove(x1)
        else:
            temp.append(x2)
            seq2.remove(x2)

    #Append remaining list to output
    if seq1 != []:
        for i in seq1:
            temp.append(i)
    if seq2 != []:
        for i in seq2:
           temp.append(i)

    return temp
            
def MergeSort(seq):
    size = len(seq)
    #Base cases w/ single or no element
    if size == 0:
        return 0
    if size == 1:
        return seq

    #Recursively split sequence
    temp1 = MergeSort(seq[0:int(size/2)])
    temp2 = MergeSort(seq[int(size/2):])
    
    return merge(temp1, temp2) #Join subsequences


def CountingSort(seq):
    largest = max(seq)
    count = [0]*(largest+1)
    out = [0]*len(seq)

    for i in seq: #Count how many of each number
        count[i] += 1
    for i in range(1,largest+1): #Running sum of how many smaller numbers
        count[i] += count[i-1]
    for i in seq:   #Place numbers in appropriate order
        out[count[i]-1] = i
        count[i] -= 1
    return out

def RadixCount(seq, digits):
    size = len(seq)
    count = [0]*10
    out = [0]*size

    #Same as counting sort but instead of looking at entire number it only looks at the 
    #least significant digit to sort hence the additional input of digits.

    #For digits 0-9, count how many numbers end in each one 
    for i in range(size): 
        j = seq[i]//digits
        count[j%10] += 1

    #Running sum of how many smaller numbers
    for i in range(1,size+1): 
        count[i] += count[i-1]

    #Place numbers in appropriate order, needs to be traversed in reverse to maintain order
    for i in range(size-1, -1, -1): 
        j = seq[i]//digits
        out[count[j%10]-1] = seq[i]
        count[j%10] -= 1
    return out

def RadixSort(seq):
    largest = max(seq)
    digits = 1
    temp = []
    for i in seq: temp.append(i)

    #Use counting sort for each digit from least significant to most
    while largest // digits:
        temp = RadixCount(temp, digits)
        digits *= 10
    return temp

a = [1, 3, 2, 5, 7, 4, 9, 7, 10]
x = [22, 21, 57, 45, 61, 32, 11]

b = MergeSort(a)
c = CountingSort(a)
d = RadixSort(a)
e = RadixSort(x)