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)
- Teaching Kids Programming – Bubble Sorting (Simple Sorting Algorithm)
- Teaching Kids Programming – MergeSort Simply Explained
- Teaching Kids Programming – QuickSort Algorithm Simply Explained
- Teaching Kids Programming – Selection Sorting (Simple Sorting Algorithm)
- Teaching Kids Programming – Insertion Sort in Python (Simple Sorting Algorithm)
- Teaching Kids Programming – Counting Sort Algorithm in Python
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Two Pointer Partition String to Most Unique SubStrings
Next Post: Array Recursive Index Algorithm By Simulation