parallel merge sort using fork, wait and shared array.

merge_sort.py

#!/usr/bin/env python3

from multiprocessing import Array
from os import fork, wait, _exit
from random import randint


def merge_sort(type, arr):
    N = len(arr)
    # create shared array
    arr = Array(type, arr, lock=False)
    cache = Array(type, N, lock=False)
    # sort
    _merge_sort(cache, arr, 0, N)
    # convert back
    return list(arr)


def _merge_sort(cache, arr, i, j):
    if j - i <= 1: _exit(0)

    # fork
    mid = (i + j) // 2
    for start, end in [(i, mid), (mid, j)]:
        if fork(): continue
        _merge_sort(cache, arr, start, end)
        _exit(0)
    wait()
    wait()

    # merge
    a, b, amax, bmax, c = i, mid, mid, j, i
    while a < amax and b < bmax:
        if arr[a] < arr[b]:
            cache[c] = arr[a]
            a += 1
        else:
            cache[c] = arr[b]
            b += 1
        c += 1
    while a < amax:
        cache[c] = arr[a]
        a += 1
        c += 1
    while b < bmax:
        cache[c] = arr[b]
        b += 1
        c += 1

    # copy from cache to arr
    for k in range(i, j):
        arr[k] = cache[k]


if __name__ == '__main__':
    # generate random array
    arr = [randint(1, 100) for i in range(20)]
    # before
    print(','.join(map(str, arr)))
    # sort
    arr = merge_sort('i', arr)
    # after
    print(','.join(map(str, arr)))