1/3/26, 11:31 AM DSA Merge Sort with Python

❯
 Tutorials  References  Exercises  Certificates  Search... Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
AVL Trees
Graphs
Linear Search
Binary Search
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Counting Sort
Radix Sort
Merge Sort

Python MySQL
MySQL Get Started
DSA Merge Sort with Python
COLOR
MySQL Create Database
❮ Previous Next ❯
MySQL Create Table PICKER
MySQL Insert
MySQL Select
MySQL Where Merge Sort
MySQL Order By
MySQL Delete The Merge Sort algorithm is a divide-and-conquer algorithm that sorts an array by first 
breaking it down into smaller arrays, and then building the array back together the correct

way so that it is sorted.

Sort

Divide: The algorithm starts with breaking up the array into smaller and smaller pieces
until one such sub-array only consists of one element.

Conquer: The algorithm merges the small pieces of the array back together by putting the
lowest values first, resulting in a sorted array.

The breaking down and building up of the array to sort the array is done recursively.

In the animation above, each time the bars are pushed down represents a recursive call,
splitting the array into smaller pieces. When the bars are lifted up, it means that two sub-
arrays have been merged together.

The Merge Sort algorithm can be described like this:

How it works:

[Link] 1/8
1/3/26, 11:31 AM DSA Merge Sort with Python
1. Divide the unsorted array into two sub-arrays, half the size of the original. ❯
 Tutorials  References  Exercises  Certificates  Upgrade Get Certified
2. Continue to divide the sub-arrays as long as the current piece of the array has more
Sign In

than one element.

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
AVL Trees
3. Merge two sub-arrays together by always putting the lowest value first.
4. Keep merging until there are no sub-arrays left.
Graphs
Linear Search
Binary Search
Bubble Sort
Take a look at the drawing below to see how Merge Sort works from a different
Selection Sort
perspective. As you can see, the array is split into smaller and smaller pieces until it is
Insertion Sort merged back together. And as the merging happens, values from each sub-array are
Quick Sort compared so that the lowest value comes first.
Counting Sort
Radix Sort
Merge Sort

Python MySQL
MySQL Get Started
MySQL Create Database
MySQL Create Table
MySQL Insert
MySQL Select
MySQL Where
MySQL Order By
MySQL Delete

Manual Run Through

Let's try to do the sorting manually, just to get an even better understanding of how
Merge Sort works before actually implementing it in a Python program.

Step 1: We start with an unsorted array, and we know that it splits in half until the sub-
arrays only consist of one element. The Merge Sort function calls itself two times, once for
each half of the array. That means that the first sub-array will split into the smallest pieces
first.

[ 12, 8, 9, 3, 11, 5, 4]
[ 12, 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8] [ 9] [ 3, 11, 5, 4]

Step 2: The splitting of the first sub-array is finished, and now it is time to merge. 8 and 9
are the first two elements to be merged. 8 is the lowest value, so that comes before 9 in
the first merged sub-array.

[Link] 2/8
1/3/26, 11:31 AM DSA Merge Sort with Python

❯
 Tutorials 
[ 12] [ 8, 9] [ 3, 11, 5, 4]
References  Exercises  Certificates  Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
AVL Trees Step 3: The next sub-arrays to be merged is [ 12] and [ 8, 9]. Values in both arrays are
Graphs compared from the start. 8 is lower than 12, so 8 comes first, and 9 is also lower than 12.
Linear Search
Binary Search [ 8, 9, 12] [ 3, 11, 5, 4]
Bubble Sort
Selection Sort
Insertion Sort Step 4: Now the second big sub-array is split recursively.

Quick Sort
[ 8, 9, 12] [ 3, 11, 5, 4]
Counting Sort
[ 8, 9, 12] [ 3, 11] [ 5, 4]
Radix Sort
[ 8, 9, 12] [ 3] [ 11] [ 5, 4]
Merge Sort

Python MySQL Step 5: 3 and 11 are merged back together in the same order as they are shown because 3
MySQL Get Started is lower than 11.
MySQL Create Database
MySQL Create Table [ 8, 9, 12] [ 3, 11] [ 5, 4]
MySQL Insert
MySQL Select
MySQL Where Step 6: Sub-array with values 5 and 4 is split, then merged so that 4 comes before 5.
MySQL Order By
MySQL Delete [ 8, 9, 12] [ 3, 11] [ 5] [ 4]
[ 8, 9, 12] [ 3, 11] [ 4, 5]

Step 7: The two sub-arrays on the right are merged. Comparisons are done to create
elements in the new merged array:

1. 3 is lower than 4
2. 4 is lower than 11
3. 5 is lower than 11
4. 11 is the last remaining value

[ 8, 9, 12] [ 3, 4, 5, 11]

Step 8: The two last remaining sub-arrays are merged. Let's look at how the comparisons
are done in more detail to create the new merged and finished sorted array:

3 is lower than 8:

Before [ 8, 9, 12] [ 3, 4, 5, 11]

After: [ 3, 8, 9, 12] [ 4, 5, 11]

Step 9: 4 is lower than 8:

Before [ 3, 8, 9, 12] [ 4, 5, 11]

After: [ 3, 4, 8, 9, 12] [ 5, 11]

Step 10: 5 is lower than 8:

Before [ 3, 4, 8, 9, 12] [ 5, 11]

After: [ 3, 4, 5, 8, 9, 12] [ 11]

[Link] 3/8
1/3/26, 11:31 AM DSA Merge Sort with Python

❯
 Tutorials  ReferencesStep Exercises
 11: Certificates
8 and 9 are lower 
than 11: Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Before [ 3, 4, 5, 8, 9, 12] [ 11]
AVL Trees
After: [ 3, 4, 5, 8, 9, 12] [ 11]
Graphs
Linear Search
Binary Search
Step 12: 11 is lower than 12:
Bubble Sort
Selection Sort Before [ 3, 4, 5, 8, 9, 12] [ 11]
Insertion Sort After: [ 3, 4, 5, 8, 9, 11, 12]
Quick Sort
Counting Sort The sorting is finished!
Radix Sort
Merge Sort
Run the simulation below to see the steps above animated:
Python MySQL
MySQL Get Started
Sort
MySQL Create Database
MySQL Create Table [ 12, 8, 9, 3, 11, 5, 4]
MySQL Insert
MySQL Select
MySQL Where
MySQL Order By

Implement Merge Sort in Python

MySQL Delete

To implement the Merge Sort algorithm we need:

1. An array with values that needs to be sorted.

2. A function that takes an array, splits it in two, and calls itself with each half of that
array so that the arrays are split again and again recursively, until a sub-array only
consist of one value.
3. Another function that merges the sub-arrays back together in a sorted way.

The resulting code looks like this:

Example Get your own Python Server

Implementing the Merge Sort algorithm in Python:

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

mid = len(arr) // 2
leftHalf = arr[:mid]
rightHalf = arr[mid:]

sortedLeft = mergeSort(leftHalf)
sortedRight = mergeSort(rightHalf)

return merge(sortedLeft, sortedRight)

def merge(left, right):

result = []
i = j = 0

while i < len(left) and j < len(right):

[Link] 4/8
1/3/26, 11:31 AM DSA Merge Sort with Python
if left[i] < right[j]: ❯
 Tutorials  References  Exercises  Certificates 
[Link](left[i]) Upgrade Get Certified Sign In
i += 1
HTML CSS JAVASCRIPT SQL PYTHON
else: JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
AVL Trees
[Link](right[j])
Graphs j += 1
Linear Search
Binary Search [Link](left[i:])
Bubble Sort [Link](right[j:])
Selection Sort
return result
Insertion Sort
Quick Sort
mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
Counting Sort mysortedlist = mergeSort(mylist)
Radix Sort print("Sorted array:", mysortedlist)
Merge Sort

Run Example »
Python MySQL
MySQL Get Started
MySQL Create Database On line 6, arr[:mid] takes all values from the array up until, but not including, the value on
MySQL Create Table index "mid".
MySQL Insert
MySQL Select On line 7, arr[mid:] takes all values from the array, starting at the value on index "mid" and
MySQL Where all the next values.
MySQL Order By
On lines 26-27, the first part of the merging is done. At this this point the values of the
MySQL Delete
two sub-arrays are compared, and either the left sub-array or the right sub-array is empty,
so the result array can just be filled with the remaining values from either the left or the
right sub-array. These lines can be swapped, and the result will be the same.

Merge Sort without Recursion

Since Merge Sort is a divide and conquer algorithm, recursion is the most intuitive code to
use for implementation. The recursive implementation of Merge Sort is also perhaps easier
to understand, and uses less code lines in general.

But Merge Sort can also be implemented without the use of recursion, so that there is no
function calling itself.

Take a look at the Merge Sort implementation below, that does not use recursion:

Example
A Merge sort without recursion

def merge(left, right):

result = []
i = j = 0

while i < len(left) and j < len(right):

if left[i] < right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1

[Link](left[i:])

[Link] 5/8
1/3/26, 11:31 AM DSA Merge Sort with Python
[Link](right[j:]) ❯
 Tutorials  References  Exercises  Certificates  Upgrade Get Certified Sign In
return result
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
AVL Trees
def mergeSort(arr):
Graphs step = 1 # Starting with sub-arrays of length 1
Linear Search length = len(arr)
Binary Search
Bubble Sort while step < length:
Selection Sort for i in range(0, length, 2 * step):
left = arr[i:i + step]
Insertion Sort
right = arr[i + step:i + 2 * step]
Quick Sort
Counting Sort merged = merge(left, right)
Radix Sort
Merge Sort # Place the merged array back into the original array
for j, val in enumerate(merged):
Python MySQL arr[i + j] = val

MySQL Get Started

step *= 2 # Double the sub-array length for the next iteration
MySQL Create Database
MySQL Create Table return arr
MySQL Insert
MySQL Select mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
MySQL Where mysortedlist = mergeSort(mylist)
print(mysortedlist)
MySQL Order By
MySQL Delete
Run Example »

You might notice that the merge functions are exactly the same in the two Merge Sort
implementations above, but in the implementation right above here the while loop inside
the mergeSort function is used to replace the recursion. The while loop does the splitting
and merging of the array in place, and that makes the code a bit harder to understand.

To put it simply, the while loop inside the mergeSort function uses short step lengths to
sort tiny pieces (sub-arrays) of the initial array using the merge function. Then the step
length is increased to merge and sort larger pieces of the array until the whole array is
sorted.

Merge Sort Time Complexity

The time complexity for Merge Sort is: O(n ⋅ log n)

And the time complexity is pretty much the same for different kinds of arrays. The
algorithm needs to split the array and merge it back together whether it is already sorted
or completely shuffled.

The image below shows the time complexity for Merge Sort.

[Link] 6/8
1/3/26, 11:31 AM DSA Merge Sort with Python

❯
 Tutorials  References  Exercises  Certificates  Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
AVL Trees
Graphs
Linear Search
Binary Search
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Counting Sort
Radix Sort
Merge Sort

Python MySQL
MySQL Get Started
Merge Sort performs almost the same every time because the array is split, and merged
MySQL Create Database
using comparison, both if the array is already sorted or not.
MySQL Create Table
MySQL Insert
MySQL Select
❮ Previous Sign in to track progress Next ❯
MySQL Where
MySQL Order By
MySQL Delete

-->
 PLUS SPACES GET CERTIFIED FOR TEACHERS

FOR BUSINESS CONTACT US

Top Tutorials Top References

HTML Tutorial HTML Reference
CSS Tutorial CSS Reference
JavaScript Tutorial JavaScript Reference
How To Tutorial SQL Reference
SQL Tutorial Python Reference
Python Tutorial [Link] Reference
[Link] Tutorial Bootstrap Reference
Bootstrap Tutorial PHP Reference
PHP Tutorial HTML Colors
Java Tutorial Java Reference
C++ Tutorial AngularJS Reference
jQuery Tutorial jQuery Reference

Top Examples Get Certified

HTML Examples HTML Certificate
CSS Examples CSS Certificate
JavaScript Examples JavaScript Certificate
How To Examples Front End Certificate
SQL Examples SQL Certificate
Python Examples Python Certificate
[Link] Examples PHP Certificate
Bootstrap Examples jQuery Certificate
PHP Examples Java Certificate
Java Examples C++ Certificate

[Link] 7/8
1/3/26, 11:31 AM DSA Merge Sort with Python
XML Examples C# Certificate
❯
 Tutorials  jQuery Examples
References  Exercises  Certificates  XML Certificate
Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
AVL Trees
     FORUM ABOUT ACADEMY
Graphs
W3Schools is optimized for learning and training. Examples might be simplified to improve reading and learning.
Linear Search
Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full correctness
Binary Search of all content. While using W3Schools, you agree to have read and accepted our terms of use, cookies and privacy policy.

Bubble Sort Copyright 1999-2026 by Refsnes Data. All Rights Reserved. W3Schools is Powered by [Link].
Selection Sort
Insertion Sort
Quick Sort
Counting Sort
Radix Sort
Merge Sort

Python MySQL
MySQL Get Started
MySQL Create Database
MySQL Create Table
MySQL Insert
MySQL Select
MySQL Where
MySQL Order By
MySQL Delete

[Link] 8/8