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.

マージソートとnlognの比較.png

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

Recommended Posts

Merge sort implementation / complexity analysis and experiment in Python
Sorting algorithm and implementation in Python
A memo about writing merge sort in Python
Explanation of edit distance and implementation in Python
RNN implementation in python
ValueObject implementation in Python
Bubble sort in Python
Custom sort in Python3
Association analysis in Python
SVM implementation in python
Regression analysis in Python
Logical symbols learned in marriage (and implementation examples in Python)
[Python] How to sort dict in list and instance in list
Principal component analysis (PCA) and independent component analysis (ICA) in python
Overview of generalized linear models and implementation in Python
Naturally sort Path in Python
Axisymmetric stress analysis in Python
python in mongodb in descending sort
Stack and Queue in Python
Simple regression analysis in Python
Neural network implementation in python
Unittest and CI in Python
Maxout description and implementation (Python)
Implementation of quicksort in Python
Sort by date in python
About Python sort () and reverse ()
Sort and output the elements in the list as elements and multiples in Python.
MIDI packages in Python midi and pretty_midi
Difference between list () and [] in Python
First simple regression analysis in Python
Difference between == and is in python
What's new in python3.9 Merge dictionaries
View photos in Python and html
HMM parameter estimation implementation in python
Mixed normal distribution implementation in python
Manipulate files and folders in Python
About dtypes in Python and Cython
Assignments and changes in Python objects
Implementation of life game in Python
Check and move directories in Python
Ciphertext in Python: IND-CCA2 and RSA-OAEP
Sort large text files in Python
Hashing data in R and Python
Function synthesis and application in Python
Export and output files in Python
Planar skeleton analysis in Python (2) Hotfix
Implementation of original sorting in Python
Simple regression analysis implementation in Keras
Reverse Hiragana and Katakana in Python2.7
Reading and writing text in Python
[GUI in Python] PyQt5-Menu and Toolbar-
Create and read messagepacks in Python
Data analysis: Easily apply descriptive and inference statistics to CSV data in Python
Implementation of particle filters in Python and application to state space models
Deep Learning from scratch-Chapter 4 tips on deep learning theory and implementation learned in Python
When specifying multiple keys in python sort
Overlapping regular expressions in Python and Java
New in Python 3.9 (2)-Sort directed acyclic graphs in Python
Differences in authenticity between Python and JavaScript
Notes using cChardet and python3-chardet in Python 3.3.1.
Differences between Ruby and Python in scope