Trusted answers to developer questions
Trusted Answers to Developer Questions

RELATED TAGS

Merge sort in Python

Educative Answers Team

Merge sort is one of the most prominent divide-and-conquer sorting algorithms in the modern era. It can be used to sort the values in any traversable data structure such as a list.

The theory

Merge sort works by splitting the input list into two halves, repeating the process on those halves, and finally merging the two sorted halves together.

1 of 17

The algorithm first moves from top to bottom, dividing the list into smaller and smaller parts until only the separate elements remain.

From there, it moves back up, ensuring that the merging lists are sorted.

Implementation

Here is the code for merge sort in Python:

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 = [54,26,93,17,77,31,44,55,20]
mergeSort(myList)
print(myList)

This is the recursive approach for implementing merge sort. The steps needed to obtain the sorted array through this method can be found below:

  • The list is divided into left and right in each recursive call until two adjacent elements are obtained.

  • Now begins the sorting process. The i and j iterators traverse the two halves in each call. The k iterator traverses the whole lists and makes changes along the way.

  • If the value at i is smaller than the value at j, left[i] is assigned to the myList[k] slot and i is incremented. If not, then right[j] is chosen.

  • This way, the values being assigned through k are all sorted.

  • At the end of this loop, one of the halves may not have been traversed completely. Its values are simply assigned to the remaining slots in the list.

And with that, the merge sort has been implemented!

Time complexity

The algorithm works in O(nlogn). This is because the list is being split in log(n) calls and the merging process takes linear time in each call.

RELATED TAGS

Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time

Copyright ©2022 Educative, Inc. All rights reserved.

soc2