How to Merge a Sort in Python

Using a merge sort in Python can speed up sorting tasks.

Sorting lists of data is a problem that has vexed programmers since the beginning of computer programming. Sorting any list of data can end up as a memory- and time-intensive task. Because of this, different sort methods have been invented to minimize the challenge and effort of sorting. One method is merge sorting. It subdivides a list recursively into singular elements and recombines the list in sorted form. Any programming language that supports recursion, such as Python, can implement a merge sort.

Things You'll Need

• Python Interpreter with Interactive Development Environment

Instructions

1. Define the "mergesort" function. This basic function calls itself recursively, splitting the list size in half with each call. Once the mergesort function hits a list with one element, the recursion stops and the element returns. As the mergesort recursion unwinds, each smaller list is merged together in sorted order. This example displays a basic mergesort function that takes a list as an argument:

   >>>def mergesort(li):

   . . . if len(li) < 2:

   . . . return li

   . . . mid = len(li) / 2

   . . . first = mergesort(li[:mid])

   . . . last = mergesort(li[mid:])

   . . . return merge(first, last)

2. Set up the merge method. This function will serve as the sorting method; it returns a sorted list of elements. The merge method takes two already-sorted lists. It then defines an internal list "sorted" that will represent the combined sorted argument lists. The merge method accomplishes this by taking the smallest element and inserting it into a new list "sorted". Once one of the lists ends, the other list is inserted in its entirety.

   >>>def merge(x, y):

   . . . sorted = []

3. Merge the lists in the merge method. The "while" loop in the example compares each list item by item, taking the smallest element and inserting it into a new list "sorted". Once one of the lists ends, the other list is inserted in its entirety, and the new sorted list is returned:

   . . . i, j = 0, 0

   . . . while i < len(x) and j < len(y):

   . . . if x[i] <= y[j]:

   . . . sorted.append(x[i])

   . . . i += 1

   . . . else:

   . . . sorted.append(y[j])

   . . . j += 1

   . . . sorted += x[I:]

   . . . sorted += y[:j]

   . . . return sorted

References

• Loyalty.org: Python Recursion
• Python.org: Data Structures