Merge Sort Array in Python (Example)

 

In this article, you’ll learn how to sort an array by the merge sort algorithm in Python.

The tutorial contains the following content:

Let’s do this!

 

Modules and Sample Data

First, we will import the array module.

import array

Then we will create a sample array to be used in the examples.

the_array = array.array('f', [-14, 25, 31, 40, -3.5, 856, 1])

Now, we are ready to show an example of how to sort an array based on the merge sort algorithm.

 

Example: Application of Merge Sort on Array

The following Python syntax shows how to define a function that sorts an array based on the merge sort algorithm. This algorithm divides the arrays at hand into smaller subarrays; then, after sorting these subarrays, it merges them in a cyclic fashion. Let’s see how to implement it in Python!

First, the array length is checked to see if it has at least one element. If that is not the case, no operation is done, which the return command ensures. This check is called stopping condition.

def merge_sort(arr):
    if len(arr) <= 1:
        return

As you see in the following code chunk, the array arr is divided into left_arr and right_arr with respect to the middle of the list mid if the length of arr is not less than one. Then the merge_sort(left_array) function call is executed, which generates a new branch for sorting the left_array. Once left_array has been sorted, the same sorting steps are followed for the right_array. Please be aware that, in each function call, the stopping condition is checked first, then the aforementioned steps are taken.

    mid = len(arr)//2                     # setting the middle index of the array
    left_arr = arr[:mid]                  # setting the left subarray
    right_arr = arr[mid:]                 # setting the right subarray
 
    merge_sort(left_arr)                  # sorting the left subarray
    merge_sort(right_arr)                 # sorting the right subarray

The following script merges the sorted subarrays into a single sorted array. At each step, the lowest element of the left and right subarrays are compared, and the lower one is inserted into the parent array. This continues until one subarray runs out of elements, and the remaining elements of the compared subarray are added to the parent array. The procedure is executed on all subarrays until the sorted version of the initial array is produced.

    i = 0                                 # initializing some loop variables
    j = 0
    x = 0
 
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:    # finding the current smallest element
            arr[x] = left_arr[i]          # assigning the element to the parent array
            i += 1                        # incrementing left array index
        else:
            arr[x] = right_arr[j]         # assigning the element to the parent array
            j += 1                        # incrementing right array index
        x += 1                            # incrementing parent array index
 
    while i < len(left_arr):              # checking if left array has more elements
        arr[x] = left_arr[i]              # assigning the element to the parent array
        i += 1                            # incrementing left array index
        x += 1                            # incrementing parent array index
 
    while j < len(right_arr):             # checking if right array has more elements
        arr[x] = right_arr[j]             # assigning the element to the parent array
        j += 1                            # incrementing right array index
        x += 1                            # incrementing parent array index

Below you can see the execution of the function using our sample data the_array.

merge_sort(the_array)
print(the_array)
# array('f', [-14.0, -3.5, 1.0, 25.0, 31.0, 40.0, 856.0])

Here is the complete code script for the merge_sort() function for your use.

def merge_sort(arr):
    if len(arr) <= 1:
        return
 
    mid = len(arr)//2                     # setting the middle index of the array
    left_arr = arr[:mid]                  # setting the left subarray
    right_arr = arr[mid:]                 # setting the right subarray
 
    merge_sort(left_arr)                  # sorting the left subarray
    merge_sort(right_arr)                 # sorting the right subarray
 
    i = 0                                 # initializing some loop variables
    j = 0
    x = 0
 
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:    # finding the current smallest element
            arr[x] = left_arr[i]          # assigning the element to the parent array
            i += 1                        # incrementing left array index
        else:
            arr[x] = right_arr[j]         # assigning the element to the parent array
            j += 1                        # incrementing right array index
        x += 1                            # incrementing parent array index
 
    while i < len(left_arr):              # checking if left array has more elements
        arr[x] = left_arr[i]              # assigning the element to the parent array
        i += 1                            # incrementing left array index
        x += 1                            # incrementing parent array index
 
    while j < len(right_arr):             # checking if right array has more elements
        arr[x] = right_arr[j]             # assigning the element to the parent array
        j += 1                            # incrementing right array index
        x += 1                            # incrementing parent array index

 

I hope this tutorial helps! You can check out the Visualization of Merge Sort in Python tutorial for further insight.

Video & Further Resources

Please have a look at the following video instruction on my YouTube channel. In the video, I’m explaining the topics of this tutorial.

 

The YouTube video will be added soon.

 

Furthermore, you might want to read the related tutorials on this website. Some tutorials can be found below.

 

In summary: You have learned in this tutorial how to sort an array by the merge sort algorithm in the Python programming language. If you have any additional questions or comments, please let me know in the comments section.

 

Ömer Ekiz Python Programming & Informatics

This page was created in collaboration with Ömer Ekiz. Look at Ömer’s author page to get more information about his professional background, a list of all his tutorials, as well as an overview on his other tasks on Statistics Globe.

 

Subscribe to the Statistics Globe Newsletter

Get regular updates on the latest tutorials, offers & news at Statistics Globe.
I hate spam & you may opt out anytime: Privacy Policy.


Leave a Reply

Your email address will not be published. Required fields are marked *

Fill out this field
Fill out this field
Please enter a valid email address.

Top