In this article I am going to walk through an array sorting algorithm called "Merge sort" in short and clear steps; hopefully to help you understand more how sorting algorithms work in Python in order to enhance your abilities to analyze and solve problems more efficiently.
Before we start
Before we start, you have to know that in order to achieve the best sorting method, and to be able to compare all methods and algorithms together in respect of time and space; Big O is the perfect measure for that.
Big O Notation is a mathematical concept used to describe the complexity of an algorithm as how much time and memory it holds.
Assuming that n is the size of the input to an algorithm, the Big O notation represents the relationship between n and the number of steps the algorithm takes to find a solution.
- The following description of some cases will help you understand and classify Big O notation accordingly:
|O(1)||Constant||fixed time/space in each time an algorithm is executed.|
|O(n)||Linear||linearly growth with data size until it reaches O (worst case)|
|O(n²)||quadratic||directly proportional to square data size "common in nested iterations"|
|O(2^n)||exponential||double growth with addition of data ex: recursive Fibonacci|
|O(log n)||logarithmic||little effect on growth while doubling data size|
Merge Sort Approach
This sorting method is based on the divide-and-conquer approach.
- divide-and-conquer Is an algorithm design paradigm in computer science that recursively breaks down a problem into two or more sub-problems until they become simple enough to be solved. The solutions to the sub-problems are then combined to give a solution to the original problem.
In Merge sort algorithm, the input integers are divided into two equal parts, then each half will be sorted alone and recursively it will be also divided into two parts and so on up until there's no more input values. After that, sorted values will be combined together again into an array.
- The Merge sort algorithm is divided into two parts:
1. A function to split the array into two parts recursively.
2. A function to merge the sorted array.
- The next Pseudocode shows how to implement the Merge sort algorithm:
ALGORITHM Mergesort(arr) DECLARE n <-- arr.length if n > 1 DECLARE mid <-- n/2 DECLARE left <-- arr[0...mid] DECLARE right <-- arr[mid...n] // sort the left side Mergesort(left) // sort the right side Mergesort(right) // merge the sorted left and right sides together Merge(left, right) ALGORITHM Merge(left, right) DECLARE i <-- 0 DECLARE j <-- 0 DECLARE result<--  while len(result) < len(left) + len(right) if left[i] <= right[j] result <-- [left[i]] i <-- i + 1 else result <-- [right[j]] j <-- j + 1 if i = left.length set remaining entries in arr to remaining values in right else set remaining entries in arr to remaining values in left
- Lets assume the input of our algorithm is the following array/list:
array = [8, 4, 23, 42, 16, 15]
- To make it more clear and easy to understand, here is a step-by-step visualization of each algorithm iteration for the array:
As you can see, the array is supposed to be sorted ascendingly by splitting the original array into two parts, then recursively dividing the parts until the result array reaches a total number of elements.
Now, lets review the steps of solving this problem so we can implement it using Python:
Define a function to split the array, check if array length is less that 2 return the array as it is.
Create a mid variable for the middle value of the array and then return the next function passing two values: left which is the array starting from begging until mid, and right starting from mid until last.
- Define another function merge with a result empty array, i and j for tracking current left, right values respectively.
- loop through left and right arrays until they fill up the result array with all elements.
- Compare values of left array with right array and append the smaller value to the result array recursively.
- Once one of the arrays are finished, add it to the other half
- Return the result array.
Here is the implementation of Python code for Merge sort approach, built upon the algorithm steps above:
def merge_sort(arr): n = len(arr) if n < 2: return arr mid = int(n/2) left = arr[:mid] right = arr[mid:] return merge(merge_sort(left), merge_sort(right)) def merge(left, right): result =  i = 0 j = 0 while len(result) < len(left) + len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 if j == len(right): result += left[i:] if i == len(left): result += right[j:] return result
Big O Notation
- Merge function takes a linear time to merge the two arrays which is O(n).
- While the Merge_sort function takes a logarithmic runtime as it calls itself (recursively) to divide the array into half in each step, which is O(log n).
Hence the total time for merge_sort function will become n(log n), which gives us a time complexity of O(n*log n) and this is the best worst case scenario for time complexity.
- Big O space complexity of merge sort method is O(n)
User Acceptance Tests
Here is a passed test of merge_sort function with different arrays:
def test_merge_sort(): arr = [8,4,23,42,16,15] assert [4, 8, 15, 16, 23, 42] == merge_sort(arr) arr2 = [20,18,12,8,5,-2] assert [-2, 5, 8, 12, 18, 20] == merge_sort(arr2) arr3 = [2,3,5,7,13,11] assert [2,3,5,7,11,13] == merge_sort(arr3) arr4 = [5,12,7,5,5,7] assert [5,5,5,7,7,12] == merge_sort(arr4)
Tools and References