Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves.
Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.
Check out the resources below for a review of Merge sort!
def merge_sort(arr): if len(arr)>1: mid = len(arr)/2 lefthalf = arr[:mid] righthalf = arr[mid:] merge_sort(lefthalf) merge_sort(righthalf) i=0 j=0 k=0 while i < len(lefthalf) and j < len(righthalf): if lefthalf[i] < righthalf[j]: arr[k]=lefthalf[i] i=i+1 else: arr[k]=righthalf[j] j=j+1 k=k+1 while i < len(lefthalf): arr[k]=lefthalf[i] i=i+1 k=k+1 while j < len(righthalf): arr[k]=righthalf[j] j=j+1 k=k+1
arr = [11,2,5,4,7,6,8,1,23] merge_sort(arr) print(arr)
[1, 2, 4, 5, 6, 7, 8, 11, 23]
If you like my post please follow me to read my latest post on programming and technology.
Factory Method is a creational design pattern that deals with the object creation. It separates…
You are given two singly linked lists that intersect at some node. Your task is…
A builder plans to construct N houses in a row, where each house can be…
Find the length of the longest absolute path to a file within the abstracted file…
You manage an e-commerce website and need to keep track of the last N order…
You are given a stream of elements that is too large to fit into memory.…