merge sort implementation
#merge sort
#the merge algorithm
def merge(L1, L2, L):
i = 0
j = 0
while i+j < len(L):
if j == len(L2) or (i < len(L1) and L1[i] < L2[j]):
L[i+j] = L1[i]
i += 1
else:
L[i+j] = L2[j]
j += 1
#main function
def merge_sort(L):
n = len(L)
if n < 2:
return # list is already sorted
# divide
mid = n // 2 #midpoint
L1 = L[0:mid] # the first half
L2 = L[mid:n] # the second half
# conquer with recursion
merge_sort(L1) # sort first sublist
merge_sort(L2) # sort second sublist
# merge result
merge(L1, L2, L)
#example
L = [7, 5, 1, 4, 2, 8, 0, 9, 3, 6]
print('Before: ', L)
merge_sort(L)
print('After: ', L)
The merge sort algorithm uses the divide and conquer technique to efficiently sort a list of elements.
Divide and conquer involves breaking down a larger problem into smaller more manageable subproblems, solving the subproblems and then merging their solutions to solve the original problem. In the case with mergesort, the algorithm breaks down the list into smaller sublists, sorts those sublists recursively, and then merges the sorted sublists back together until the entire list is sorted
Merge sort has time complexity of O(nlogn)
in both average and worst case scenarios, this makes it one of the fastest sorting algorithms and consequently, one of the most sought after.
Merge sort is stable, meaning that it preserves the relative order of equal elements in the original list.
Algorithm Description
Assuming we have a list L , the basic steps followed by merge sort are as highlighted below:
 divide **  If **L has zero or one element, it is already sorted, immediately return L. Otherwise, divide L's elements between two sublists, L_{1} and L_{2}. Where, L1 contains first half of the elements and L2 the rest..
 conquer  Recursively sort sublists L1 and L2.

merge  Combine the elements in a sorted state and put them back to
L
.
Example
Consider if we want to sort the following list using merge sort.
In the first step of merge sort, the list will be recursively divided into individual sublists. This means that the list will be split into two sublists and then each of the sublists will be split into two more sublists, and so on until each sublist contains only a single element. The following figure demonstrates the splitting phase:
After the divide step is over, we need to sort each sublist and then recursively merge it with the other sorted sublists. This is known as the "conquer" step.
At the beginning of the conquer step, each sublists is made up of a single element. Logically, a list with only one element is already sorted. Sublists with more than a single elements will have to be sorted before they are combined.
Merge sort implementation
In this section, we will implement the merge sort algorithm using functions.
For the sake of clarity, we will split the algorithm into two functions, merge()
and merge_sort()
. The merge()
function will be responsible for combining two already sorted sublists into a single sorted list. The merge_sort()
function is where the main logic of the algorithm will go.
The merge() function
#L is the list while L1 and L2 are the sublists.
def merge(L1, L2, L):
i = j = 0
while i+j < len(L):
if j == len(L2) or (i < len(L1) and L1[i] < L2[j]):
L[i+j] = L1[i]
i += 1
else:
L[i+j] = L2[j]
j += 1
#example
L = [2, 7, 4, 0, 6, 5]
L1 = [2, 4, 7]
L2 = [0, 6, 5]
merge(L1, L2, L)
print(L)
The merge()
function above takes in two sorted sublists(L1
andL2
) and puts their elements back to the original list(L
) in a sorted state. It does so by determining from which sublist the next item should be taken before inserting the picked item back to list L
. For clarity, let us look at the function statement by statement:

i = j = 0
 This statement initializes two distinct variables,i
andj
each with a value of0
. The two variablesi
, andj
represents the position of the current element inL1
andL2
, respectively. 
while i+j < len(L):
 Loop until the value ofi + j
is greater than the length of the list. Note that at this point, the merge operation will be complete. 
if j == len(L2) or (i < len(L1) and L1[i] < L2[j]): L[i+j] = L1[i] i += 1
else: L[i+j] = L2[j] j += 1
The j == len(L2)
condition checks if there is elements to be picked in L2
, remember thatj
represents the position of the current element in L2
, thus if it is equal to len(L2)
, it means that we have reached the end of L2
, so we pick the next element from L1
and insert it toL
.
Due to the presence of or
, the second condition i.e (i < len(L1) and L1[i] < L2[j])
will only be tested if the first condition, i.e (j == len(L2))
fails, it means that L2
still has element . So we pick and insert intoL
the smaller of the sublists' current element and then increment either i
orj
depending on whose sublist's element was picked.
The else
statement also caters for when L1
has no more elements.
After implementing the merge(
) function, the implementation of the merge_sort()
function become easier.
implementmerge_sort()
#the implementation of merge() is omitted, refer to the previous snippet.
def merge_sort(L):
n = len(L)
if n < 2:
return # list is already sorted
# divide
mid = n // 2 #midpoint
L1 = L[0:mid] # the first half
L2 = L[mid:n] # the second half
# conquer
merge_sort(L1) # recursively sort first sublist
merge_sort(L2) # recursively sort second sublist
# merge
merge(L1, L2, L)
#usage example
L = [99, 9, 0, 2, 1, 0, 1, 100, 2, 8, 7, 4, 3, 2]
merge_sort(L)
print(L)
[2, 0, 0, 1, 1, 2, 2, 3, 4, 7, 8, 9, 99, 100]
Themerge_sort()
function does not return any value because the sorting happens to the original list.
The entire merge sort implementation is as shown below:
#merge sort implementation
def merge(L1, L2, L):
i = 0
j = 0
while i+j < len(L):
if j == len(L2) or (i < len(L1) and L1[i] < L2[j]):
L[i+j] = L1[i]
i += 1
else:
L[i+j] = L2[j]
j += 1
def merge_sort(L):
n = len(L)
if n < 2:
return # list is already sorted
# divide
mid = n // 2 #midpoint
L1 = L[0:mid] # the first half
L2 = L[mid:n] # the second half
# conquer with recursion
merge_sort(L1) # sort first sublist
merge_sort(L2) # sort second sublist
# merge result
merge(L1, L2, L)
#usage example
L = [99, 9, 0, 2, 1, 0, 1, 100, 2, 8, 7, 4, 3, 2]
merge_sort(L)
print(L)
Complexity analysis
The time complexities of merge sort with a list of size n
, are as outlined below:

Best case 
O(nlogn
) , this happens when the input list is already sorted. 
Average case 
O(nlogn)
, when the input list is randomly sorted. 
Worst case 
O(nlogn)
, when the input list is reverse sorted.
Space complexity
Merge sort has a space complexity ofO(n)
due to the space occupied by the sublists.
Top comments (0)