Home » Merge Sort example in python

# Merge Sort example in python

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

### Operation

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.

### Code Example

```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]
```