Notes
The Mergesort breaks down a list in half recursively, and then merge them back in the correct order.
Example
Part I: Dividing the list of elements
6, 8, 5, 7, 2, 4 The list to be sorted
6, 8, 5 | 7, 2, 4
6, 8 | 5 | 7, 2 | 4
6 | 8 | 5 | 7 | 2 | 4
Part II: Merging
6 | 8 | 5 | 7 | 2 | 4
6, 8 | 5 | 7, 2 | 4 Since 6 is already less than 8, no change
6, 8 | 5 | 7, 2 | 4
5, 6, 8 | 7, 2 | 4 Sort 6, 8 and 5 in ascending order
5, 6, 8 | 7, 2 | 4
5, 6, 8 | 2, 7 | 4 Sort 7 and 2 in ascending order
5, 6, 8 | 2, 7 | 4
5, 6, 8 | 2, 4, 7 Sort 2, 7 and 4 in ascending order
5, 6, 8 | 2, 4, 7
2, 4, 5, 6, 7, 8 Sort 5, 6, 8 and 2, 4, 7 in ascending order
Sample Code in Python
#Sorting the list [6, 8, 5, 7, 2, 4] in ascending order
list1 = [6, 8, 5, 7, 2, 4]
def mergesort(sort_list):
mergesort_helper(sort_list, 0, len(sort_list) - 1)
def mergesort_helper(sort_list, first, last):
middle = (first + last) // 2
if first < last:
mergesort_helper(sort_list, first, middle)
mergesort_helper(sort_list, middle+1, last)
merge(sort_list, first, middle, last)
def merge(sort_list, first, middle, last):
temp_list = []
list1_pointer = first
list2_pointer = middle + 1
for i in range(last - first + 1):
if list1_pointer > middle:
temp_list.append(sort_list[list2_pointer])
list2_pointer += 1
continue
elif list2_pointer > last:
temp_list.append(sort_list[list1_pointer])
list1_pointer += 1
continue
if sort_list[list1_pointer] <= sort_list[list2_pointer]:
temp_list.append(sort_list[list1_pointer])
list1_pointer += 1
else:
temp_list.append(sort_list[list2_pointer])
list2_pointer += 1
pointer = 0
for i in range(first, last + 1):
sort_list[i] = temp_list[pointer]
pointer += 1
mergesort(list1)
print(list1)