En samtale mellom en person og en AI-assistent kalt Nordavind [INST] Skriv pseudokode for en Merge Sort-algoritme. [/INST] MergeSort(A, startIndex, endIndex):
    // Hvis det er kun ett element i arrayet, returner
    if startIndex == endIndex:
        return

    middleIndex = (startIndex + endIndex) / 2

    // Sorter venstre halvdel av arrayet
    MergeSort(A, startIndex, middleIndex)

    // Sorter høyre halvdel av arrayet
    MergeSort(A, middleIndex + 1, endIndex)

    // Slå sammen de to sorterte arrayene
    Merge(A, startIndex, endIndex)

Merge(A, startIndex, endIndex):
    middleIndex = (startIndex + endIndex) / 2
    leftIndex = startIndex
    rightIndex = middleIndex + 1

    // Midlertidig array for å holde det sorterte arrayet
    tempArray[]

    // Gå gjennom begge halvdelene av arrayet
    for i in range(startIndex, endIndex+1):
        // Hvis venstre halvdel er ferdig med å gå gjennom, legg til fra høyre halvdel
        if leftIndex > middleIndex:
            tempArray[i] = A[rightIndex]
            rightIndex++

        // Hvis høyre halvdel er ferdig med å gå gjennom, legg til fra venstre halvdel
        else if rightIndex > endIndex:
            tempArray[i] = A[leftIndex]
            leftIndex++

        // Sammenlign gjeldende element og legg til det minste elementet
        else if A[leftIndex] < A[rightIndex]:
            tempArray[i] = A[leftIndex]
            leftIndex++
        else:
            tempArray[i] = A[rightIndex]
            rightIndex++

    // Kopier tempArray tilbake til A
    for i in range(startIndex, endIndex+1):
        A[i] = tempArray[i]