# 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.

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:

Furthermore, you could read the related tutorials on this homepage. I have published several articles already.

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.

Subscribe to the Statistics Globe Newsletter