Mergesort Cutaway

Sorting an array can be done in different ways. It ranges from the simpler bubble sort to more complicated ones such as the merge sort.

What is mergesort?

Bottom-up mergesort starts by continuously dividing an array into smaller sublists until each sublist is of size 1. Then, pairs of individual sublists are merged in a sorted order, to form arrays of size 2. This process continues until only one merged list remains. This final list is the sorted array.

The term mergesort is a combination of two subwords: merge - that is to merge smaller arrays into bigger ones and sort - meaning to rearrange terms in order – ascending or descending.

Why mergesort?

Mergesort is one of the efficient sorting algorithms. It outshines the capabilities of bubble sort by a large margin. Mergesort has best and worst case complexity of \(O(n log n)\) compared to the even worse complexity of the bubble sort going up to \(O(n^2)\).

Where is mergesort used?

Mergesort is one of the typical sorting algorithms used for sorting arrays or sequences of numbers. It is the method used by many builtin functions of programming languages due to its efficiency and short sorting time.

Mergesort implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#!/usr/bin/env python3

import operator

class Mergesort:
    # Implements the bottom-up merge sort algorithm.
    
    def __init__(self, ascending=True, cutaway=False):
        self._ascending = ascending
        self._cutaway = cutaway
                    
    def _rsplit(self, arr):
        # Recursively splits an array and returns subarrays of size 1
        if self._cutaway:
            print('<< s p l i t >>',arr)
        _arr = arr.copy()
        if len(_arr) <= 1:   # edge condition
            return [_arr]

        mid = len(_arr)//2 # the 'middle' dividing point
        
        # now array as two parts -- one slice is [:mid] and another [mid:]
        return [*self._rsplit(_arr[:mid]), *self._rsplit(_arr[mid:])]
            
    def _merge(self,frag1,frag2):
        # Implements a sorted merge with another fragment.        
        # Returns a merge of two sorted arrays
        _sarr1 = frag1.copy()
        _sarr2 = frag2.copy()
        
        # If 1 fragment is empty, return the other fragment
        if not _sarr1:
            return _sarr2
        
        if not _sarr2:
            return _sarr1
        
        # Choose comparison operator based on ascending flag.
        comp_opr = [operator.ge,operator.le][self._ascending]
        pre = _sarr1.pop(0) if comp_opr(_sarr1[0],_sarr2[0]) else _sarr2.pop(0)        
        
        return [pre] + self._merge(_sarr1,_sarr2)        
        
    def get_sorted(self, ary):
        # input unsorted array, returns mergesorted array.
        if len(ary) <= 1:
            return ary
        
        # Split operation: Create a list of arrays with one element each.
        frag_list = self._rsplit(ary)
        # Alternatively, [[e] for e in ary]

        # Merge operation
        while(len(frag_list)>1):
            # Remove element pairs from frag_list,merge them and append to frag_list.
            if self._cutaway:
                print(">>merge<<", frag_list)
            frag_list.append(self._merge(frag_list.pop(0), frag_list.pop(0)))                               
        
        return frag_list[0]   # The only element here is the final merged/sorted list
    
    def __repr__(self):
        # Printable representation of object.
        return f'{self.__class__.__name__}:ascending={self._ascending},cutaway={self._cutaway}'
  

if __name__ == "__main__":

    arr3 = list(range(10,0,-1))
    
    sorter = Mergesort(cutaway=True,ascending=True)
    print(sorter)
    print(sorter.get_sorted(arr3))
    # End

The _rsplit() function recursively splits the array into sublists of 1 and adds them to a list of sublists (frag_list). The _merge() recursively merges these sublists, two at a time and appends them to frag_list and continues until just one sublist remains. This final sublist is the sorted list.

Mergesort:ascending=True,cutaway=True
<< s p l i t >> [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
<< s p l i t >> [10, 9, 8, 7, 6]
<< s p l i t >> [10, 9]
<< s p l i t >> [10]
<< s p l i t >> [9]
<< s p l i t >> [8, 7, 6]
<< s p l i t >> [8]
<< s p l i t >> [7, 6]
<< s p l i t >> [7]
<< s p l i t >> [6]
<< s p l i t >> [5, 4, 3, 2, 1]
<< s p l i t >> [5, 4]
<< s p l i t >> [5]
<< s p l i t >> [4]
<< s p l i t >> [3, 2, 1]
<< s p l i t >> [3]
<< s p l i t >> [2, 1]
<< s p l i t >> [2]
<< s p l i t >> [1]
>>merge<< [[10], [9], [8], [7], [6], [5], [4], [3], [2], [1]]
>>merge<< [[8], [7], [6], [5], [4], [3], [2], [1], [9, 10]]
>>merge<< [[6], [5], [4], [3], [2], [1], [9, 10], [7, 8]]
>>merge<< [[4], [3], [2], [1], [9, 10], [7, 8], [5, 6]]
>>merge<< [[2], [1], [9, 10], [7, 8], [5, 6], [3, 4]]
>>merge<< [[9, 10], [7, 8], [5, 6], [3, 4], [1, 2]]
>>merge<< [[5, 6], [3, 4], [1, 2], [7, 8, 9, 10]]
>>merge<< [[1, 2], [7, 8, 9, 10], [3, 4, 5, 6]]
>>merge<< [[3, 4, 5, 6], [1, 2, 7, 8, 9, 10]]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

The above cutaway view first shows how the array is split and later how pairs of sublists get merged and appended to the list of lists until the final sorted list is generated.

Top-down mergesort implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#! /usr/bin/env python3
# Top-down mergesort implementation

def merge(larr, rarr):
    # Merge two sorted arrays    
    assert larr and rarr, f'merge: array argument length cannot be zero'
    
    print(f'{larr} >> merge << {rarr}', end='')
    
    resarr = []    
    while (larr and rarr):  # both arrays no-empty
        resarr.append(larr.pop(0) if larr[0] <= rarr[0] else rarr.pop(0))
        # ascending sort, exit loop when one array empties

    assert bool(larr) ^ bool(rarr), f'merge: of larr and rarr only one has to be 0 length'
        
    resarr.extend(larr if larr else rarr)
    
    print(f' ---> {resarr}')
    return resarr

    
def mergesort(arr):

    if len(arr) <= 1:   # base case
        return arr
    mid = len(arr)//2
    print(f'{arr} ---> {arr[:mid]} << s p l i t >> {arr[mid:]}')
    return merge(mergesort(arr[:mid]),mergesort(arr[mid:]))

    
if __name__ == "__main__":
    ary = [10,9,8,7,6,5,4,3,2,1]
    print(mergesort(ary))
    

The output of this program is as follows:

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] ---> [10, 9, 8, 7, 6] << s p l i t >> [5, 4, 3, 2, 1]
[10, 9, 8, 7, 6] ---> [10, 9] << s p l i t >> [8, 7, 6]
[10, 9] ---> [10] << s p l i t >> [9]
[10] >> merge << [9] ---> [9, 10]
[8, 7, 6] ---> [8] << s p l i t >> [7, 6]
[7, 6] ---> [7] << s p l i t >> [6]
[7] >> merge << [6] ---> [6, 7]
[8] >> merge << [6, 7] ---> [6, 7, 8]
[9, 10] >> merge << [6, 7, 8] ---> [6, 7, 8, 9, 10]
[5, 4, 3, 2, 1] ---> [5, 4] << s p l i t >> [3, 2, 1]
[5, 4] ---> [5] << s p l i t >> [4]
[5] >> merge << [4] ---> [4, 5]
[3, 2, 1] ---> [3] << s p l i t >> [2, 1]
[2, 1] ---> [2] << s p l i t >> [1]
[2] >> merge << [1] ---> [1, 2]
[3] >> merge << [1, 2] ---> [1, 2, 3]
[4, 5] >> merge << [1, 2, 3] ---> [1, 2, 3, 4, 5]
[6, 7, 8, 9, 10] >> merge << [1, 2, 3, 4, 5] ---> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Note that the recursive mergesort function recurses all the way to the point where the array length is just 1. This is the base case. When all these recursive calls return, they merge the (now sorted) split array segments in the correct order and assemble the complete sorted array.