Sorteeralgoritme: Merge Sort (9 ptn)

In deze vraag moet je merge sort zelf schrijven en er enkele vragen over beantwoorden. Je mag het onderstaande kader kopiëren in het invoerveld om op de vragen te antwoorden.

Let erop dat je de antwoorden op theorievragen als commentaarlijnen laat staan. Dan zal Dodona ook effectief controleren of jouw implementatie van merge sort werkt.

Vragen

1. Schrijf de functie merge_sort(lijst) die de ingevoerde lijst sorteert. Je krijgt de functie merge(lijst1, lijst2) cadeau, die 2 gesorteerde lijsten samenvoegt tot 1 gesorteerde lijst.
2. Geef de tijdscomplexiteit van merge sort.
3. Welk soort algoritme is merge_sort? Hoe zie je dat?
4. Geef de term voor de soort strategie die merge sort hanteert om efficiënt lange lijsten te sorteren.
5. Python gebruikte lang TimSort als standaard sorteeralgoritme. Op welke 2 vlakken verschilt TimSort van merge sort?

def merge(lijst1, lijst2):
    ans = []
    a = 0
    b = 0
    while a < len(lijst1) and b < len(lijst2):
        a1 = lijst1[a]
        b1 = lijst2[b]
        if a1 < b1:
            ans.append(a1)
            a += 1
            continue
        ans.append(b1)
        b += 1
        continue
    if a < len(lijst1):
        return ans + lijst1[a:]
    return ans + lijst2[b:]

# Vraag 1
def merge_sort(lijst):
	# Hier jouw code!
	pass


# Vraag 2
# Complexiteit: <jouw antwoord>

# Vraag 3
# Soort algoritme: <jouw antwoord>
# Verklaring: <jouw antwoord>

# Vraag 4
# Strategie: <jouw antwoord>

# Vraag 5
# Verschil 1: <jouw antwoord>
# Verschil 2: <jouw antwoord>