1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def merge(left_lst, right_lst):
    merged = []
    while left_lst or right_lst:
        if not left_lst:
            merged.extend(right_lst)
            return merged
        elif not right_lst:
            merged.extend(left_lst)
            return merged
        elif left_lst[0] <= right_lst[0]:
            merged.append(left_lst.pop(0))
        else:
            merged.append(right_lst.pop(0))
    return merged


def mergesort(lst):
    if len(lst) < 2:
        return lst
    else:
        mid = len(lst) // 2
        left_sorted = mergesort(lst[:mid])
        right_sorted = mergesort(lst[mid:])
        return merge(left_sorted, right_sorted)


if __name__ == "__main__":
    print("Without repeated values:")
    values = [9, 1, 10, 2, 8, 7, 3, 6, 4, 5]
    print(f"Before sorting:\n{values}")
    values = mergesort(values)
    print(f"After sorting:\n{values}")
    
    print("\nWith repeated values:")
    values = [7, 9, 10, 4, 8, 1, 10, 1, 8, 7]
    print(f"Before sorting:\n{values}")
    values = mergesort(values)
    print(f"After sorting:\n{values}")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

"""Kommentera koden på de markerade platserna.

SKRIV KOMMENTARERNA SOM ATT DE VORE RIKTIGA KOMMENTARER I DIN KOD.

- Skriv docstrings som följer PEP257 för varje funktion: "The docstring for a
  function or method should summarize its behavior and document its arguments,
  return value(s), side effects, exceptions raised, and restrictions on when it
  can be called (all if applicable). Optional arguments should be indicated. It
  should be documented whether keyword arguments are part of the interface.".
  Se https://peps.python.org/pep-0257/ för mer information.
- Lämna kvar existerande block-kommentarerna och skriv din kommentar under dem
  (se exempel på kurshemsidan).
- Inlinekommentarerna ska vara formulerade som hjälp till andra programmerare
  som läser koden. Skriv INTE dina kommentarer formulerade som svar på
  frågorna. Dvs. skriv inte "Syftet med villkoret är att ..." utan skriv
  kommentaren som om frågan inte funnits där.


# Tips

- Börja med block-kommentarerna i funktionen innan ni skriver funktionens
  docstring.
- Börja med block-kommentarerna i looparna innan ni skriver kommentaren för
  loopen.
"""


def mergesort(alist):
    """Skriv docstring för funktionen."""
    if len(alist) > 1:
        # Kommentera tilldelningarna. Vad är syftet med dessa?
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        # Kommentera vad dessa anrop till mergesort gör, vad är resultatet
        # efter att de körts?
        mergesort(lefthalf)
        mergesort(righthalf)

        # Kommentera vad dessa tre variabler används för.
        i = 0
        j = 0
        k = 0
        
        # Kommentera syftet med denna loop. Vad är resultatet efter att loopen
        # är klar?
        while i < len(lefthalf) and j < len(righthalf):
            # Kommentera vad villkorssatsen gör (båda grenar)
            if lefthalf[i] <= righthalf[j]:
                alist[k] = lefthalf[i]
                i = i + 1
            else:
                alist[k] = righthalf[j]
                j = j + 1
            k = k + 1

        # Kommentera syftet med denna loop
        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i = i + 1
            k = k + 1

        # Kommentera syftet med denna loop
        while j < len(righthalf):
            alist[k] = righthalf[j]
            j = j + 1
            k = k + 1