Merge Sort Algorithm

Merge Sort Algorithm

Step-By-Step With Python

Overview

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:
Big OComplexityDescription
O(1)Constantfixed time/space in each time an algorithm is executed.
O(n)Linearlinearly growth with data size until it reaches O (worst case)
O(n²)quadraticdirectly proportional to square data size "common in nested iterations"
O(2^n)exponentialdouble growth with addition of data ex: recursive Fibonacci
O(log n)logarithmiclittle 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.

divide-conquer.webp

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.

Pseudocode

  • 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:

merge sort.jpg

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.

Algorithm

Now, lets review the steps of solving this problem so we can implement it using Python:

  1. Define a function to split the array, check if array length is less that 2 return the array as it is.

  2. 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.

  3. Define another function merge with a result empty array, i and j for tracking current left, right values respectively.
  4. loop through left and right arrays until they fill up the result array with all elements.
  5. Compare values of left array with right array and append the smaller value to the result array recursively.
  6. Once one of the arrays are finished, add it to the other half
  7. Return the result array.

Code Implementation

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

Verification Process


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)

Source Code

GitHub


Tools and References