Merge Sort Counting Inversions in Python (Example)
In this article, I’ll demonstrate how to implement the merge sort algorithm counting inversions in the Python programming language. The merge sort algorithm counting inversions sorts an array by calculating how many pairs (i,j) are there in a list where i < j and list[i] > list[j] to calculate the number of switches required to sort the array.
Table of contents:
It’s time to dive into the tutorial:
Introducing Example Data
We use the following data as a basis for this Python programming tutorial.
my_list = [2, 4, 1, 3, 5] # initializing sample integer list
Let’s see the implementation of the algorithm using my_list!
Example: Implementation of Merge Sort Counting Inversions
Here’s how to implement this algorithm in Python. Firstly, count_inversions() checks the size of the list to see if it is large enough to have it split into two sublists. If not, the function returns the current list in the execution.
If so, just like the standard recursive merge sort algorithm, the function generates two function calls with left_half and right_half as the input parameters. The function calls return the sorted versions of these sublists and the inversion counts.
Finally, the sublists are merged, and the inversion counts between the two sublists are added to compute the total inversion count.
def count_inversions(my_list): # size check for the list if len(my_list) <= 1: return my_list, 0 mid = len(my_list) // 2 # calculate left and right sublist inversions left_half, left_inversions = count_inversions(my_list[:mid]) right_half, right_inversions = count_inversions(my_list[mid:]) # calculate the inversions between two sublists merged_list, inversions = merge(left_half, right_half) # computing total inversions return merged_list, left_inversions + right_inversions + inversions
Let’s see now how the merge function operates used in count_inversions()!
def merge(left_half, right_half): merged_list = [] inversions = 0 i = 0 j = 0 while i < len(left_half) and j < len(right_half): # checking if left sublist has the lower element if left_half[i] <= right_half[j]: merged_list.append(left_half[i]) i += 1 # else clause is executed if the right sublist has the lower element else: merged_list.append(right_half[j]) j += 1 # incrementing found inversion count inversions += len(left_half) - i merged_list.extend(left_half[i:]) merged_list.extend(right_half[j:]) return merged_list, inversions
The merge() function takes two sorted lists as input and merges them into one sorted list while counting the number of inversions.
It iterates over the left and right halves of the list using the indexes i and j for each, respectively. It compares the current elements of the left and right halves and appends the smaller element to initially defined merged_list.
If the element of the right list is not bigger than the element of the left list, it increments the inversions variable by the number of remaining elements in the left half.
Finally, it appends the remaining elements from the left and right list halves to the merged_list and returns it along with the total number of inversions.
Have a look at the console output below. It displays that the implementation correctly sorted the sample list and determined that there were 3 inversions in the list.
sorted_list, inversions = count_inversions(my_list) print("Sorted list:", sorted_list) # Sorted list: [1, 2, 3, 4, 5] print("Number of inversions:", inversions) # Number of inversions: 3
Here is the complete code for this tutorial for your use:
my_list = [2, 4, 1, 3, 5] # initializing sample integer list def count_inversions(my_list): # size check for the list if len(my_list) <= 1: return my_list, 0 mid = len(my_list) // 2 # calculate left and right sublist inversions left_half, left_inversions = count_inversions(my_list[:mid]) right_half, right_inversions = count_inversions(my_list[mid:]) # calculate the inversions between two sublists merged_list, inversions = merge(left_half, right_half) # computing total inversions return merged_list, left_inversions + right_inversions + inversions def merge(left_half, right_half): merged_list = [] inversions = 0 i = 0 j = 0 while i < len(left_half) and j < len(right_half): # checking if left sublist has the lower element if left_half[i] <= right_half[j]: merged_list.append(left_half[i]) i += 1 # else clause is executed if the right sublist has the lower element else: merged_list.append(right_half[j]) j += 1 # incrementing found inversion count inversions += len(left_half) - i merged_list.extend(left_half[i:]) merged_list.extend(right_half[j:]) return merged_list, inversions sorted_list, inversions = count_inversions(my_list) print("Sorted list:", sorted_list) # Sorted list: [1, 2, 3, 4, 5] print("Number of inversions:", inversions) # Number of inversions: 3
Video, Further Resources & Summary
Have a look at the following video on my YouTube channel. I illustrate the Python programming codes of this article in the video:
The YouTube video will be added soon.
Furthermore, you could read the related tutorials on this homepage. I have published several articles already.
- Merge Sort in Ascending & Descending Order in Python
- Iterative Bottom Up Merge Sort in Python
- Function & Library for Merge Sort in Python
- k-way Merge Sort in Python in R
- Python Programming Overview
Summary: This page has explained how to implement the merge sort algorithm counting inversions in the Python programming language. Let me know in the comments in case you have additional comments and/or questions. In addition, please subscribe to my email newsletter to get updates on new articles.
This page was created in collaboration with Ömer Ekiz. Have a 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 of his other tasks on Statistics Globe.
I’m Joachim Schork. On this website, I provide statistics tutorials as well as code in Python and R programming.
