<jupyter_start><jupyter_text>Merge Sort[link](https://www.algoexpert.io/questions/Merge%20Sort)  My Solution<jupyter_code># O(nlog(n)) time | O(nlog(n)) space
def mergeSort(array):
    # Write your code here.
    length = len(array)
    if length == 1:
        return array
    
    breakPointIdx = length // 2
    sortedSubarrayLeft = mergeSort(array[:breakPointIdx])
    sortedSubarrayRight = mergeSort(array[breakPointIdx:])
    newArray = [None for _ in range(length)]
    
    idxLeft, idxRight = 0, 0
    while idxLeft < len(sortedSubarrayLeft) and idxRight < len(sortedSubarrayRight):
        idx = idxLeft + idxRight
        if sortedSubarrayLeft[idxLeft] < sortedSubarrayRight[idxRight]:
            newArray[idx] = sortedSubarrayLeft[idxLeft]
            idxLeft += 1
        else:
            newArray[idx] = sortedSubarrayRight[idxRight]
            idxRight += 1
    
    while idxLeft < len(sortedSubarrayLeft):
        idx = idxLeft + idxRight
        newArray[idx] = sortedSubarrayLeft[idxLeft]
        idxLeft += 1
        
    while idxRight < len(sortedSubarrayRight):
        idx = idxLeft + idxRight
        newArray[idx] = sortedSubarrayRight[idxRight]
        idxRight += 1
    
    return newArray
# O(nlog(n)) time | O(n) space
def mergeSort(array):
    # Write your code here.
    auxi = [_ for _ in array]
    lastIdx = len(array) - 1
    breakPoint = lastIdx // 2
    helper(array, auxi, 0, breakPoint, breakPoint + 1, len(array) - 1)
    return array

    
def helper(mainArray, auxiArray, leftStart, leftEnd, rightStart, rightEnd):
    if leftStart > leftEnd or rightStart > rightEnd:
        return
    leftBreakPoint = (leftStart + leftEnd) // 2
    helper(auxiArray, mainArray, leftStart, leftBreakPoint, leftBreakPoint + 1, leftEnd)
    rightBreakPoint = (rightStart + rightEnd) // 2
    helper(auxiArray, mainArray, rightStart, rightBreakPoint, rightBreakPoint + 1, rightEnd)
    
    doMerge(mainArray, auxiArray, leftStart, leftEnd, rightStart, rightEnd)
    
def doMerge(mainArray, auxiArray, leftStart, leftEnd, rightStart, rightEnd):
    leftIdx = leftStart
    rightIdx = rightStart
    for idx in range(leftStart, rightEnd + 1):
        if leftIdx <= leftEnd and rightIdx <= rightEnd:
            if auxiArray[leftIdx] < auxiArray[rightIdx]:
                mainArray[idx] = auxiArray[leftIdx]
                leftIdx += 1
            else:
                mainArray[idx] = auxiArray[rightIdx]
                rightIdx += 1
            continue
        
        if leftIdx <= leftEnd:
            mainArray[idx] = auxiArray[leftIdx]
            leftIdx += 1
            continue
        if rightIdx <= rightEnd:
            mainArray[idx] = auxiArray[rightIdx]
            rightIdx += 1
            continue
# O(nlog(n)) time | O(n) space
def mergeSort(array):
    # Write your code here.
    auxi = [_ for _ in array]
    lastIdx = len(array) - 1
    helper(array, auxi, 0, lastIdx)
    return array

    
def helper(mainArray, auxiArray, startIdx, endIdx):
    if startIdx == endIdx:
        return
    midIdx = (startIdx + endIdx) // 2
    helper(auxiArray, mainArray, startIdx, midIdx)
    helper(auxiArray, mainArray, midIdx + 1, endIdx)
    doMerge(mainArray, auxiArray, startIdx, midIdx, endIdx)
    
def doMerge(mainArray, auxiArray, startIdx, midIdx, endIdx):
    leftIdx, rightIdx = startIdx, midIdx + 1
    leftEnd, rightEnd = midIdx, endIdx
    for idx in range(startIdx, endIdx + 1):
        if leftIdx <= leftEnd and rightIdx <= rightEnd:
            if auxiArray[leftIdx] < auxiArray[rightIdx]:
                mainArray[idx] = auxiArray[leftIdx]
                leftIdx += 1
            else:
                mainArray[idx] = auxiArray[rightIdx]
                rightIdx += 1
            continue
        
        if leftIdx <= leftEnd:
            mainArray[idx] = auxiArray[leftIdx]
            leftIdx += 1
            continue
        if rightIdx <= rightEnd:
            mainArray[idx] = auxiArray[rightIdx]
            rightIdx += 1
            continue
# O(nlog(n)) time | O(n) space
def mergeSort(array):
    # Write your code here.
    mergeSortHelper(array, 0, len(array) - 1)
    return array


def mergeSortHelper(array, startIdx, endIdx):
    if startIdx >= endIdx:
        return
    middleIdx = (startIdx + endIdx) // 2
    mergeSortHelper(array, startIdx, middleIdx)
    mergeSortHelper(array, middleIdx + 1, endIdx)
    doSort(array, startIdx, middleIdx + 1, endIdx)

def doSort(array, startIdx, rightHalfStartIdx, endIdx):
    i = startIdx
    j = rightHalfStartIdx
    combinedArray = []
    while i <= rightHalfStartIdx - 1 and j <= endIdx:
        if array[i] < array[j]:
            combinedArray.append(array[i])
            i += 1
        else:
            combinedArray.append(array[j])
            j += 1

    combinedArray += array[i:rightHalfStartIdx] + array[j:endIdx + 1]
    for i, x in enumerate(combinedArray):
        array[startIdx + i] = x<jupyter_output><empty_output><jupyter_text>Expert Solution<jupyter_code># Best: O(nlog(n)) time | O(nlog(n)) space
# Average: O(nlog(n)) time | O(nlog(n)) space
# Worst: O(nlog(n)) time | O(nlog(n)) space
def mergeSort(array):
    if len(array) == 1:
        return array
    middleIdx = len(array) // 2
    leftHalf = array[:middleIdx]
    rightHalf = array[middleIdx:]
    return mergeSortedArrays(mergeSort(leftHalf), mergeSort(rightHalf))

def mergeSortedArrays(leftHalf, rightHalf):
    sortedArray = [None] * (len(leftHalf) + len(rightHalf))
    k = i = j = 0
    while i < len(leftHalf) and j < len(rightHalf):
        if leftHalf[i] <= rightHalf[j]:
            sortedArray[k] = leftHalf[i]
            i += 1
        else:
            sortedArray[k] = rightHalf[j]
            j += 1
        k += 1
    while i < len(leftHalf):
        sortedArray[k] = leftHalf[i]
        i += 1
        k += 1
    while j < len(rightHalf):
        sortedArray[k] = rightHalf[j]
        j += 1
        k += 1
    return sortedArray
# Best: O(nlog(n)) time | O(n) space
# Average: O(nlog(n)) time | O(n) space
# Worst: O(nlog(n)) time | O(n) space
def mergeSort(array):
    if len(array) <= 1:
        return array
    auxiliaryArray = array[:]
    mergeSortHelper(array, 0, len(array) - 1, auxiliaryArray)
    return array

def mergeSortHelper(mainArray, startIdx, endIdx, auxiliaryArray):
    if startIdx == endIdx:
        return
    middleIdx = (startIdx + endIdx) // 2
    mergeSortHelper(auxiliaryArray, startIdx, middleIdx, mainArray)
    mergeSortHelper(auxiliaryArray, middleIdx + 1, endIdx, mainArray)
    doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray)

def doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray):
    k = startIdx
    i = startIdx
    j = middleIdx + 1
    while i <= middleIdx and j <= endIdx:
        if auxiliaryArray[i] <= auxiliaryArray[j]:
            mainArray[k] = auxiliaryArray[i]
            i += 1
        else:
            mainArray[k] = auxiliaryArray[j]
            j += 1
        k += 1
    while i <= middleIdx:
        mainArray[k] = auxiliaryArray[i]
        i += 1
        k += 1
    while j <= endIdx:
        mainArray[k] = auxiliaryArray[j]
        j += 1
        k += 1<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10788669813940573, 'fraction_numerical': 0.009164121077478478, 'mean_word_length': 2.451365596550072, 'pattern_counts': {'":': 0, '<': 38, '<?xml version=': 0, '>': 12, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, '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': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '425343', 'license': 'MIT', 'n_tokens_mistral': 2381, 'n_tokens_neox': 2279, 'n_words': 582, 'path': 'algoExpert/merge_sort/solution.ipynb', 'repo_name': 'maple1eaf/learning_algorithm', 'size': '7202'}