Teaching Kids Programming – Merge Sort Algorithm Simply Explained (Python)


Teaching Kids Programming: Videos on Data Structures and Algorithms

In a few days ago, we talked about how to merge two sorted list, the Python code to demonstrate the algorithm is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def mergeTwo(a, b):
    i, j, la, lb = 0, 0, len(a), len(b)
    res = []
    while i < la and j < lb:
        if a[i] < b[j]:
            res.append(a[i])
            i += 1
        else:
            res.append(b[j])
            j += 1
    if i < la:
        res += a[i:]
    else:
        res += b[j:]
    return res
def mergeTwo(a, b):
    i, j, la, lb = 0, 0, len(a), len(b)
    res = []
    while i < la and j < lb:
        if a[i] < b[j]:
            res.append(a[i])
            i += 1
        else:
            res.append(b[j])
            j += 1
    if i < la:
        res += a[i:]
    else:
        res += b[j:]
    return res

MergeSort Algorithm in Python

Based on this we can recursive apply merging sorting algorithm to a list. We continuously divide the list into equal two parts. When the partition size is small enough (one element or none), we know it is by natural sorted. Then we start merge these small partitions into bigger partitions until we get the entire list sorted.

1
2
3
4
5
6
7
def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    first = mergeSort(arr[:mid])
    second = mergeSort(arr[mid:])
    return mergeTwo(first, second)
def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    first = mergeSort(arr[:mid])
    second = mergeSort(arr[mid:])
    return mergeTwo(first, second)

The merge sort algorithms run at O(NLogN) time (best, average and worst cases) and takes O(N) space.

The merge sorting algorithm is a stable sorting algorithm – where it maintains the relative equal-key orders.

Sorting Algorithms (Teaching Kids Programming Tutorials)

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
488 words
Last Post: Two Pointer Partition String to Most Unique SubStrings
Next Post: Array Recursive Index Algorithm By Simulation

The Permanent URL is: Teaching Kids Programming – Merge Sort Algorithm Simply Explained (Python)

Leave a Reply