Merge sort implementation / complexity analysis and experiment in Python

This time, I will talk about merge sort (using the divide-and-conquer method) of the sort algorithm. A sort algorithm is an algorithm that sorts elements in a data structure in ascending or descending order, and merge sort is one of the most commonly seen algorithms.

Explanation of the algorithm

In merge sort, sorting is basically done using an array, but as the name implies, the array is divided and then mixed. While doing this mixing, we will compare and sort each element. As a result, you get a sorted array.

Split

First, when splitting, find the value in the middle of the array with mid = (low + high) / 2. For example, when the length of the array is n, mid = (0 + (n-1)) / 2 is the middle value, and it is divided into two arrays from 0 to mid and mid + 1 to n-1. Is repeated and the division ends when the length of the array becomes 1. In the division, each array is divided into two arrays, so one long array becomes the parent like a binary tree structure, and two short arrays of the same length are the children. Imagine that this created a log (n) tree with a depth of 2 as the base.

Governance

When governing, the first elements of the two child arrays are compared and placed at the beginning of the parent list. It then increments the accessed index of the list containing the selected element by one, compares the second element with the first element of one, and stores it in the next index of the parent list. The value of the index selected in this way is incremented, the work of storing in the parent list is repeated up to the last element of either one of the child lists, and the elements of the list with the remaining elements are stored in order. By repeating this in order from the end node of the tree structure to the root node, the array sorted by the last root node is completed.

I will post the website that explains in an easy-to-understand manner with a graph at the end.

Implementation

I have implemented a merge sort function briefly, so I will explain it. I added line numbers from 1 in the comments on the right side of each line.

merge_sort.py

def merge(array):                                   # line1
    mid = len(array)                                # line2
    if mid > 1:                                     # line3
        left = merge(array[:(mid/2)])               # line4
        right = merge(array[(mid/2):])              # line5
        array = []                                  # line6
        while len(left) != 0 and len(right) != 0:   # line7
            if left[0] < right[0]:                  # line8
                array.append(left.pop(0))           # line9
            else:                                   # line10
                array.append(right.pop(0))          # line11
        if len(left) != 0:                          # line12
            array.extend(left)                      # line13
        elif len(right) != 0:                       # line14
            array.extend(right)                     # line15
    return array                                    # line16

-I made it assuming that the value taken by the parameter in line1 is an array containing only integers in the element.

-I asked for the value of the array length with line2, but it is a little different from the above explanation because I created a new array every time I split it with Python. In the case of an array such as JAVA, it is an invariant object and it is divided while calculating the index number of one array, so please find it by the method described above.

-In line3, it is judged whether the length of the array is longer than 1 and if it is long, the code from line4 to line15 is executed, and if it is short, the array is returned as it is as a return value.

-In lines 4 and 5, the function is called by giving the parameter an array that recursively slices the parent list in half.

-As you can see from the code so far, by calling the function recursively, the array is divided until it becomes 1.

The reason I'm emptying the parent array in line6 is that I'll use the method append () (add an element to the end of the list) when I put values into the list after this. The original array already contained some elements and I thought it would be inconvenient to add elements.

-Line7 used a loop, but it will continue to loop unless one of the lists is empty.

-Compare the first elements of both arrays on lines 8-11, delete the first element of the array containing smaller elements, and add it to the end of the parent array. Continue this process until one of the lists is empty.

-In line12 ~ 15, one list becomes empty when the loop of line7 ends, but the other list leaves at least one element, so the remaining elements of either array are put together in the parent list. In addition to.

-In line16, return each sorted array as a return value, sort to the parent array of each array, and when the root node is reached, return all the elements of the array given to the parameter in the sorted state. I will.

Computational complexity

Let T (n) be the total complexity of the merge sort, where n is the number of elements in the array or the length of the array. Since T (0) and T (1) do nothing, the amount of calculation is 0. In merge sort, the array is halved and merge sort is called recursively, so T (n / 2) does this twice with the amount of calculation (line 4 and 5) when it is called recursively, so T (n / 2) ) + T (n / 2) = 2T (n / 2) is when both are called (line4 ~ 5). In addition to this, merge sort loops n-1 times in the worst case, so the total complexity is T (n) = 2T (n / 2) + n -1. Now we know the amount of calculation when the length of the array of merge sort is n, but since merge sort is called recursively by halving the array, T (n / 2), T (n / 4), T (n / 8) ・ ・ ・ ・ ・ ・ ・ ・ ・ T (n / (2 ^ (k-1))) will also be investigated. k is the number of times it is called recursively, starting with k = 1. T(n/2) = 2T(n/4) + n/2 - 1, T(n/4) = 2T(n/8) + n/4 - 1, T(n/8) = 2T(n/16) + n/8 - 1, ・ ・ ・ ・ ・ T(n/2^(k-1)) = 2T(n/2^k) + n/2^(k-1) - 1 Is the amount of calculation when k> = 1.

Substituting this into the equation for T (n) gives: T(n) = 2(2T(n/4) + n/2 - 1) + n - 1 = 4T(n/4) + 2n - (1 + 2) = 4(2T(n/8) + n/4 - 1) + 2n - (1 + 2) = 8T(n/8) + 3n - (1 + 2 + 4) = 8(2T(n/16) + n/8 - 1) + 3n - (1 + 2 + 4) = 8T(n/8) + 4n - (1 + 2 + 4 + 8) ・ ・ ・ ・ ・ = 2 ^ kT (n / 2 ^ k) + k * n-(1 + 2 + 4 + ・ ・ ・ ・ ・ + 2 ^ (k-1)) It will be.

with this T (n) = 0, if n = 0,1 T (n) = 2 ^ kT (n / 2 ^ k) + (k * n --k)-(1 + 2 + 4 + ・ ・ ・ ・ ・ + 2 ^ (k-1)), It turns out that if 2 <= n <= k.

Here, the fact that the recursive call is made k times means that there are k layers in the tree structure, and 2 ^ k can be said to be the value of n in the k layer. Therefore, when n = 2 ^ k and this is solved for k, then k = log (n), and when these are substituted into the equation of T (n), T (n) = nT (2 ^ k / 2 ^ k) + log (n) * n --log (n)-(1 + 2 + 4 + ・ ・ ・ ・ ・ + 2 ^ (log (n) -1) )) = nT(1) + nlog(n) - log(n) - (2^log(n) - 1) = nlog(n) - log(n) - (2^log(n) - 1)

The first term goes from T (1) = 0 to n * 0 = 0, and the last term comes from the sum formula (see Wikipedia). Since nlog (n)> 2 ^ log (n), the complexity order is O (nlog (n)). By the way, in merge sort, both the average complexity and the best complexity are the same as the worst complexity.

Graphing

Since the average time was actually calculated and graphed, I will put up the source code and graph.

merge_sort.py

import math
import random
import time
import matplotlib.pyplot as plt

#Copy the merge sort function here

sumOfTime = 0
sumPltList = []
nlognList = []
list1 = []
#Loop to make array lengths 0-3000
for i in range(3000):
    #Loop to merge sort 100 times for each array of length i
    for j in range(100):
        #0 for each index~Enter a random number from 100000
        for k in range(i):
            list1.append(random.randint(0,100000))
        #Time before merge sort
        t0 = time.clock()
        merge(list1)
        #Time after merge sort
        t1 = time.clock()
        #Empty the array for the next merge sort
        list1 = []
        #Sum of differences in time when merge sort was performed
        sumOfTime += t1 - t0
    #Average value of 100 merge sorts
    sumOfTime /= 100
    #The average time is stored in the list, and 2000000 is the same as the book, so there is no basis.
    sumPltList.append(sumOfTime*2000000)
    # log(0)Dealing with ilog(i)Store i in the list for comparison
    if i != 0:
        nlognList.append(i*math.log(i)/math.log(2))
    else:
        nlognList.append(0.0)
    #Reset the sum of time every 100 times
    sumOfTime = 0
#Merge sort and nlog(n)Draw a curve
plt.plot(sumPltList, "r-", label = "Merge_Sort")
plt.plot(nlognList, "g-", label = "O(nlogn)")
#Show label in top left
plt.legend(loc=2)
#Label on x-axis and y-axis
plt.xlabel('number of elements in a list')
plt.ylabel('time be taken')
#Graph display
plt.show()

I multiplied 2000000 by the average time by looking at the results up to the array of length 99 and adjusted the book tail, but the graph below shows what happens with the results up to 3000 length.

Since the computational complexity values for lengths 100 to 3000 are also close to the nlog (n) values, the computational complexity experiments can be said to be successful.

This time I explained, implemented, and analyzed the merge sort algorithm, but if you find something wrong or unclear, please comment or email me. Thank you. Next time I'll implement Python statements or other algorithms in Python. Thank you for reading until the end!

Merge sort link: http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/merge-sort.html