1/3/26, 4:00 PM DSA Merge Sort with Python
Tutorials References Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
DSA Merge Sort with Python
❮ Previous Next ❯
Merge Sort
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
[Link] 1/12
1/3/26, 4:00 PM DSA Merge Sort with Python
Divide: The algorithm starts with breaking up the array into smaller and smaller pieces until
Tutorials References Exercises
one such sub-array only consists of one element.
Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
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:
1. Divide the unsorted array into two sub-arrays, half the size of the original.
2. Continue to divide the sub-arrays as long as the current piece of the array has more
than one element.
3. Merge two sub-arrays together by always putting the lowest value first.
4. Keep merging until there are no sub-arrays left.
Take a look at the drawing below to see how Merge Sort works from a different perspective.
As you can see, the array is split into smaller and smaller pieces until it is merged back
together. And as the merging happens, values from each sub-array are compared so that the
lowest value comes first.
[Link] 2/12
1/3/26, 4:00 PM DSA Merge Sort with Python
Tutorials References Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
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
[Link] 3/12
1/3/26, 4:00 PM DSA Merge Sort with Python
first merged sub-array.
Tutorials References Exercises Sign In
[ 12] [ 8, 9] [ 3, 11, 5, 4]
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
Step 3: The next sub-arrays to be merged is [ 12] and [ 8, 9]. Values in both arrays are
compared from the start. 8 is lower than 12, so 8 comes first, and 9 is also lower than 12.
[ 8, 9, 12] [ 3, 11, 5, 4]
Step 4: Now the second big sub-array is split recursively.
[ 8, 9, 12] [ 3, 11, 5, 4]
[ 8, 9, 12] [ 3, 11] [ 5, 4]
[ 8, 9, 12] [ 3] [ 11] [ 5, 4]
Step 5: 3 and 11 are merged back together in the same order as they are shown because 3
is lower than 11.
[ 8, 9, 12] [ 3, 11] [ 5, 4]
Step 6: Sub-array with values 5 and 4 is split, then merged so that 4 comes before 5.
[ 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:
[Link] 4/12
1/3/26, 4:00 PM DSA Merge Sort with Python
3 is lower than 8:
Tutorials References Exercises Sign In
Before [ 8, 9, 12] [ 3, 4, 5, 11]
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
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]
Step 11: 8 and 9 are lower than 11:
Before [ 3, 4, 5, 8, 9, 12] [ 11]
After: [ 3, 4, 5, 8, 9, 12] [ 11]
Step 12: 11 is lower than 12:
Before [ 3, 4, 5, 8, 9, 12] [ 11]
After: [ 3, 4, 5, 8, 9, 11, 12]
The sorting is finished!
Run the simulation below to see the steps above animated:
Sort
[ 12, 8, 9, 3, 11, 5, 4]
[Link] 5/12
1/3/26, 4:00 PM DSA Merge Sort with Python
Implement
Tutorials Merge
References Sort in Python
Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
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):
if left[i] < right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1
[Link](left[i:])
[Link](right[j:])
[Link] 6/12
1/3/26, 4:00 PM DSA Merge Sort with Python
return result
Tutorials References Exercises Sign In
mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
HTML CSS
mysortedlist JAVASCRIPT SQL
= mergeSort(mylist) PYTHON JAVA PHP HOW TO [Link] C
print("Sorted array:", mysortedlist)
Run Example »
On line 6, arr[:mid] takes all values from the array up until, but not including, the value on
index "mid".
On line 7, arr[mid:] takes all values from the array, starting at the value on index "mid" and
all the next values.
On lines 26-27, the first part of the merging is done. At this this point the values of the 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])
[Link] 7/12
1/3/26, 4:00 PM DSA Merge Sort with Python
i += 1
Tutorials
else: References Exercises Sign In
[Link](right[j])
HTML
CSS
j += 1JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
[Link](left[i:])
[Link](right[j:])
return result
def mergeSort(arr):
step = 1 # Starting with sub-arrays of length 1
length = len(arr)
while step < length:
for i in range(0, length, 2 * step):
left = arr[i:i + step]
right = arr[i + step:i + 2 * step]
merged = merge(left, right)
# Place the merged array back into the original array
for j, val in enumerate(merged):
arr[i + j] = val
step *= 2 # Double the sub-array length for the next iteration
return arr
mylist = [3, 7, 6, -10, 15, 23.5, 55, -13]
mysortedlist = mergeSort(mylist)
print(mysortedlist)
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.
[Link] 8/12
1/3/26, 4:00 PM DSA Merge Sort with Python
Merge
Sort
Tutorials Time Complexity
References Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
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.
Merge Sort performs almost the same every time because the array is split, and merged
using comparison, both if the array is already sorted or not.
❮ Previous Sign in to track progress Next ❯
[Link] 9/12
1/3/26, 4:00 PM DSA Merge Sort with Python
Tutorials References Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
COLOR PICKER
REMOVE ADS
Python - Variables - [Link]
Click on ► to watch the video
[Link] 10/12
1/3/26, 4:00 PM DSA Merge Sort with Python
Tutorials References Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
-->
PLUS SPACES
GET CERTIFIED FOR TEACHERS
FOR BUSINESS CONTACT US
Top Tutorials
[Link] 11/12
1/3/26, 4:00 PM DSA Merge Sort with Python
HTML Tutorial
Tutorials CSS Tutorial
References
JavaScript Tutorial
Exercises Sign In
How To Tutorial
HTML
CSS SQL Tutorial SQL
JAVASCRIPT PYTHON JAVA PHP HOW TO [Link] C
Python Tutorial
[Link] Tutorial
Bootstrap Tutorial
PHP Tutorial
Java Tutorial
C++ Tutorial
jQuery Tutorial
Top References
HTML Reference
CSS Reference
JavaScript Reference
SQL Reference
Python Reference
[Link] Reference
Bootstrap Reference
PHP Reference
HTML Colors
Java Reference
AngularJS Reference
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
XML Examples C# Certificate
jQuery Examples XML Certificate
FORUM ABOUT ACADEMY
W3Schools is optimized for learning and training. Examples might be simplified to improve reading and
learning.
Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full
correctness
of all content. While using W3Schools, you agree to have read and accepted our terms of use, cookies
and privacy policy.
Copyright 1999-2026 by Refsnes Data. All Rights Reserved. W3Schools is Powered by [Link].
[Link] 12/12