A merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.
Merge sort is a divide and conquer algorithm
Conceptually, a merge sort works as follows:
Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
def mergeSort(myList): if len(myList) > 1: mid = len(myList) // 2 left = myList[:mid] right = myList[mid:] # Recursive call on each half mergeSort(left) mergeSort(right) # Two iterators for traversing the two halves i = 0 j = 0 # Iterator for the main list k = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: # The value from the left half has been used myList[k] = left[i] # Move the iterator forward i += 1 else: myList[k] = right[j] j += 1 # Move to the next slot k += 1 # For all the remaining values while i < len(left): myList[k] = left[i] i += 1 k += 1 while j < len(right): myList[k]=right[j] j += 1 k += 1 myList = [26,78,14,92,57,44,37,58,26] mergeSort(myList) print(myList)
When you run this you will see this
>>> %Run mergesort.py [14, 26, 26, 37, 44, 57, 58, 78, 92]
Read more at hhttps://en.wikipedia.org/wiki/Merge_sort
code is available at https://github.com/programmershelp/maxpython/blob/main/code%20example/mergesort.py