Sorting Techniques in Python

def bubbleSort(arr):
    """
    Sorts an array using the Bubble Sort algorithm.
 
    :param arr: The input array to be sorted.
    :return: The sorted array.
    """
    N = len(arr)
    for i in range(N):
        for j in range(0, N - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

def selectionSort(arr):
    """
    Sorts an array using the Selection Sort algorithm.
 
    :param arr: The input array to be sorted.
    :return: The sorted array.
    """
    N = len(arr)
    for i in range(N):
        minI = i
        for j in range(i + 1, N):
            if arr[minI] > arr[j]:
                minI = j
        arr[minI], arr[i] = arr[i], arr[minI]
    return arr

def selectionSort(arr):
    """
    Sorts an array using the Selection Sort algorithm.
 
    :param arr: The input array to be sorted.
    :return: The sorted array.
    """
    N = len(arr)
    for i in range(N):
        minI = i
        for j in range(i + 1, N):
            if arr[minI] > arr[j]:
                minI = j
        arr[minI], arr[i] = arr[i], arr[minI]
    return arr

def insertionSort(arr):
    """
    Sorts an array using the Insertion Sort algorithm.
 
    :param arr: The input array to be sorted.
    :return: The sorted array.
    """
    N = len(arr)
    for i in range(N):
        for j in range(i, -1, -1):
            if j > 0 and arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
    return arr

def mergeList(list1, list2):
    """
    Merges two sorted lists into a single sorted list.
 
    :param list1: The first sorted list.
    :param list2: The second sorted list.
    :return: The merged sorted list.
    """
    i = j = k = 0
    N1 = len(list1)
    N2 = len(list2)
    res = [0] * (N1 + N2)
    while i < N1 and j < N2:
        if list1[i] < list2[j]:
            res[k] = list1[i]
            i += 1
        else:
            res[k] = list2[j]
            j += 1
        k += 1
    while i < N1:
        res[k] = list1[i]
        i += 1
        k += 1
    while j < N2:
        res[k] = list2[j]
        k += 1
        j += 1
    return res
 
def mergeSort1(arr):
    """
    Sorts an array using the Merge Sort algorithm.
 
    :param arr: The input array to be sorted.
    :return: The sorted array.
    """
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergeSort1(arr[:mid])
    right = mergeSort1(arr[mid:])
    return mergeList(left, right)
 

def mergeList2(arr, l, mid, r):
    """
    Merges two sorted portions of an array into a single sorted portion.
 
    :param arr: The input array.
    :param l: The left index of the array.
    :param mid: The middle index of the array.
    :param r: The right index of the array.
    """
    list1 = []
    list2 = []
    for i in range(l, mid + 1):
        list1.append(arr[i])
    for j in range(mid + 1, r + 1):
        list2.append(arr[j])
    i = 0
    j = 0
    k = l
    N1 = len(list1)
    N2 = len(list2)
    while i < N1 and j < N2:
        if list1[i] < list2[j]:
            arr[k] = list1[i]
            i += 1
        else:
            arr[k] = list2[j]
            j += 1
        k += 1
    while i < N1:
        arr[k] = list1[i]
        i += 1
        k += 1
    while j < N2:
        arr[k] = list2[j]
        k += 1
        j += 1
 
def mergeSort2(arr, l, r):
    """
    Sorts an array using the Merge Sort algorithm.
 
    :param arr: The input array to be sorted.
    :param l: The left index of the array.
    :param r: The right index of the array.
    """
    if l >= r:
        return
    mid = l + (r - l) // 2
    mergeSort2(arr, l, mid)
    mergeSort2(arr, mid + 1, r)
    mergeList2(arr, l, mid, r)

def quickSort(arr, si, ei):
    """
    Sorts an array using the Quick Sort algorithm.
	:param arr: The input array to be sorted.
	:param si: The starting index.
	:param ei: The ending index.
	"""
	if si >= ei:
		return
	pivotI = partition(arr, si, ei)
	quickSort(arr, si, pivotI - 1)
	quickSort(arr, pivotI + 1, ei)

def partition(arr, si, ei):
    """
    Partitions an array for Quick Sort.
 
    :param arr: The input array to be partitioned.
    :param si: The starting index.
    :param ei: The ending index.
    :return: The pivot index.
    """
    pivot = arr[si]
    i = si
    j = ei
    while i < j:
        while i < ei and pivot >= arr[i]:
            i += 1
        while j > 0 and pivot < arr[j]:
            j -= 1
        if i > j:
            break
        arr[i], arr[j] = arr[j], arr[i]
    arr[si], arr[j] = arr[j], arr[si]
    return j