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.
- Sort List of datetime Objects in Python
- Merge Sort List in Python
- Visualization of Merge Sort in Python
- Pseudocode for Merge Sort in Python
- Function & Library for Merge Sort in Python
- Python Programming Language
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.
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.