odd_even_merge_sort.py

#!/usr/bin/python3

import random

#Create a sort list of numbers. Numbers must be sorted in
#the growing order is initially odd, and then even numbers.
#For sorting use the merging algorithm.

odd, even = [], []

def merge_sort(l):
    """Recursive merge sort."""
    if len(l) > 1:
        mid = len(l) // 2
        left = l[:mid]
        right = l[mid:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                l[k] = left[i]
                i += 1
            else:
                l[k] = right[j]
                j += 1
            k += 1

        if i < len(left):
            l[k: k + len(left[i:])] = left[i:]
        if j < len(right):
            l[k: k + len(right[j:])] = right[j:]

lst = random.sample(range(1, 100), 10)
print("Input list: {}".format(lst))

for item in lst:
    if item % 2 != 0:
        odd.append(item)
    else:
        even.append(item)

merge_sort(odd)
merge_sort(even)
print("Output list:",odd + even)