1
def insertion_sort(seq):
2
    length = len(seq)
3
    counter = 1
4
    while counter < length:
5
        key = seq[counter]
6
        former = counter - 1
7
        while former > -1 and seq[former] > key:
8
            seq[former+1] = seq[former]
9
            former -= 1
10
        seq[former+1] = key
11
        counter += 1
12

13
sequence = [5, 2, 4, 6, 1, 3]
14
insertion_sort(sequence)
15
print(sequence)

1
def selection_sort(seq):
2
    for num_counter, num_temp in enumerate(seq):
3
        min_number = num_temp
4
        min_pos = num_counter
5
        for min_counter, min_temp in enumerate(seq[num_counter+1:]):
6
            if min_number > min_temp:
7
                min_number = min_temp
8
                min_pos = min_counter + num_counter + 1
9
        seq[num_counter], seq[min_pos] = seq[min_pos], seq[num_counter]
10

11
sequence = [5, 2, 4, 6, 1, 3]
12
selection_sort(sequence)
13
print(sequence)

1
def merge_sort(seq):
2
    length = len(seq)
3
    if length < 2:
4
        return seq
5
    mid = length // 2
6
    s1 = merge_sort(seq[:mid])
7
    s2 = merge_sort(seq[mid:])
8
    templ = []
9
    i, j = 0, 0
10
    while i < len(s1) and j < len(s2):
11
        if s1[i] < s2[j]:
12
            templ.append(s1[i])
13
            i += 1
14
        else:
15
            templ.append(s2[j])
16
            j += 1
17
    templ += s1[i:]
18
    templ += s2[j:]
19
    return templ
20

21
sequence = [5, 2, 4, 6, 1, 3]
22
print(merge_sort(sequence))

1
def enumerate_reversed(sequence, start=None):
2
    n = len(sequence)-1 if start is None else start
3
    for elem in reversed(sequence):
4
        yield n, elem
5
        n -= 1
6

7
def find_max_crossing_subarray(array, mid):
8
    left_max, left_pos, left_sum = array[mid-1], mid-1, 0
9
    for left_elem_idx, left_elem in enumerate_reversed(array[:mid]):
10
        left_sum += left_elem
11
        if left_sum > left_max:
12
            left_pos = left_elem_idx
13
    right_max, right_pos, right_sum = array[mid], mid, 0
14
    for right_elem_idx, right_elem in enumerate(array[mid:]):
15
        right_sum += right_elem
16
        if right_sum > right_max:
17
            right_pos = right_elem_idx
18
    return array[left_pos:mid+right_pos+1]
19

20
def find_maximum_subarray(array):
21
    if len(array) == 1:
22
        return array
23
    else:
24
        mid = len(array) // 2
25
        left_array = find_maximum_subarray(array[:mid])
26
        right_array = find_maximum_subarray(array[mid:])
27
        cross_array = find_max_crossing_subarray(array, mid)
28

29
        left_sum, right_sum, cross_sum = sum(left_array), sum(right_array), sum(cross_array)
30
        if left_sum > right_sum and left_sum > cross_sum:
31
            return left_array
32
        elif right_sum > left_sum and right_sum > cross_sum:
33
            return right_array
34
        return cross_array
35

36
test_array = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
37
maximum_array = find_maximum_subarray(test_array)
38
print(maximum_array)