q7.py

import random

def SelectPivotPair(L):
    randNumbers = random.sample(L, 5) # Choose 5 random numbers from L
    randNumbers.sort()
    return (randNumbers[1], randNumbers[-2]) # Return P0 and P1

def ThreePartition(L, P0, P1):
    L0 = []
    L1 = []
    L2 = []
    for number in L: # Iterate through L
        if number <= P0:
            L0.append(number) # Add to L0 if number is less than or equal to P0
        elif number <= P1:
            L1.append(number) # Add to L1 if number is less than or equal to P1 and greater than P0
        else:
            L2.append(number) # Add to L2 if number is greater than P1
    return (L0, L1, L2)

def ThreeWayQuickSort(L):
    if len(L) <= 10: # Recursive base case
        L.sort()
        return L
    (P0, P1) = SelectPivotPair(L)
    (L0, L1, L2) = ThreePartition(L, P0, P1)
    return ThreeWayQuickSort(L0) + ThreeWayQuickSort(L1) + ThreeWayQuickSort(L2) # Return the recursively sorted partitions of L and concatenate them