SortingAlgorithmsVisualizer/algorithms/merge_sort.py at master · m3xw3ll/SortingAlgorithmsVisualizer · GitHub

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
def merge_sort(a, start, end):
    """
    Function to recursively devide the array
    :param a: shuffled array
    :param start: startindex in array
    :param end: endindex in array
    :return: rearranged array
    """
    if end <= start:
        return

    mid = start + ((end - start + 1) // 2) - 1
    yield from merge_sort(a, start, mid)
    yield from merge_sort(a, mid + 1, end)
    yield from merge(a, start, mid, end)
    yield a


def merge(a, start, mid, end):
    """
    In-place Merge Sort
    :param a: shuffled array
    :param start: startindex in array
    :param mid: midindex in array
    :param end: endindex in array
    :return: rearranged array
    """
    merged = []
    left_idx = start
    right_idx = mid + 1

    while left_idx <= mid and right_idx <= end:
        if a[left_idx] < a[right_idx]:
            merged.append(a[left_idx])
            left_idx += 1
        else:
            merged.append(a[right_idx])
            right_idx += 1

    while left_idx <= mid:
        merged.append(a[left_idx])
        left_idx += 1

    while right_idx <= end:
        merged.append(a[right_idx])
        right_idx += 1

    for i, sorted_val in enumerate(merged):
        a[start + i] = sorted_val
        yield a