Merge Sort Dictionary in Python (Example)

In this article, I’ll demonstrate how to implement the merge sort algorithm to sort a dictionary in the Python programming language.

The tutorial contains one example of implementing the merge sort algorithm for a dictionary. To be more specific, the content of the tutorial looks as follows:

Let’s dig in…

Creation of Example Data

The following data will be used as a basis for this Python tutorial:

sample_dictionary = {'b': 2, 'c': 3, 'a': 1, 'e': 5, 'd': 4}

Without further ado, let’s get straight into the implementation!

Example: Implementation of Merge Sort for Dictionary

First, we need to define a function to perform the merge sort operation. In its essence, it is a function that takes a dictionary as its input and returns the sorted state of the dictionary.

It starts by checking if the length of the dictionary is less than or equal to 1. If the size is not larger than 1, it returns the dictionary as it is. If the dictionary has more than one element, it is divided into two halves using the middle index mid.

Here we use the enumerate() function to assign index numbers to the keys which we utilize to split the key/value pairs into halves in the splitting phase. Then, the merge_sort() function is called recursively on each half with the stopping condition of the initial size check.

def merge_sort(dictionary):
                     # base case
    if len(dictionary) <= 1:                     # checking if the dictionary needs sorting
        return dictionary
 
    mid = len(dictionary) // 2
    left_half = {}
    right_half = {}
    for index, key in enumerate(dictionary):     # keys are given index numbers and split in two groups
        if index < mid:
            left_half[key] = dictionary[key]     # forming the left half dictionary
        else:
            right_half[key] = dictionary[key]    # forming the right half dictionary
 
    left_half = merge_sort(left_half)            # recursive call for the left half
    right_half = merge_sort(right_half)          # recursive call for the right half
 
    return merge(left_half, right_half)          # merging the two sorted halves

Here we use recursive function calling which is a programming technique indicating that a function call is written inside its own definition. In this implementation of the merge sort algorithm, initially, the function is called with the original list. This function execution then calls the function for each left and right half of the original list. These calls go on until the given list of the function call is a single element, or in other words, the stopping condition is met.

Each function call ends with its list being sorted. In each function call, once the left_half and right_half are sorted, they are merged using the merge() function of which the function content is shown below.

def merge(left_half, right_half):
    result = {}
    left_keys = list(left_half.keys())
    right_keys = list(right_half.keys())
    i = 0
    j = 0
    while i < len(left_keys) and j < len(right_keys):
        if left_keys[i] < right_keys[j]:         # executed if the left half has the lower element
            result[left_keys[i]] = left_half[left_keys[i]]
            i += 1
        else:                                    # executed if the right half has the lower element
            result[right_keys[j]] = right_half[right_keys[j]]
            j += 1
    while i < len(left_keys):                    # adding remaining elements of left half
        result[left_keys[i]] = left_half[left_keys[i]]
        i += 1
    while j < len(right_keys):                   # adding remaining elements of right half
        result[right_keys[j]] = right_half[right_keys[j]]
        j += 1
    return result

The merge function first creates an empty dictionary named result. Then it checks the lowest unchecked element of the left half and right half and adds the lower element to the result dictionary. Once it goes through the halves entirely, the remaining elements of the other half are added to result, which is returned at the end of the execution.

print(merge_sort(sample_dictionary))             # printing the sorted dictionary
# {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

Finally, we can execute the merge_sort() function with our sample dictionary and see that the function indeed returns the sorted state of the input.

Video & Further Resources

I have recently released a video on my YouTube channel, which demonstrates the Python syntax of this page. You can find the video below:

The YouTube video will be added soon.

Additionally, you could read the other tutorials on this website.

• Merge Sort List in Python
• Iterative Bottom Up Merge Sort in Python
• Function & Library for Merge Sort in Python
• k-way Merge Sort in Python
• All Python Programming Examples

This article has illustrated how to sort a dictionary with merge sort in Python. Don’t hesitate to let me know in the comments section, if you have additional questions.

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.