4 min read

Merge sort is considered among the most prominent divide-and-conquer sorting algorithms. It is mainly used to sort the values in any traversable data structure such as a list.

Merge sort algorithm in simple words

  • Merge sort works by splitting the given list into two halves, repeating the process on those halves till a single element, and finally merging the two sorted halves together.
  • Merge sort algorithm first moves from top to bottom, then dividing the list into smaller and smaller parts until only the separate elements remain.
  • From there, it moves back toward an upward direction, ensuring that the merging lists are sorted.
Merge sort Gif

Now it’s time for its implementation in Python code 🙂

Python Code for Merge Sort

# Merge Sort Published on Freshlybuilt.com

#Function for merge operation
def merge(left_half, right_half):
    result_lst = []
    while len(left_half) != 0 and len(right_half) != 0:
        if left_half[0] < right_half[0]:
            result_lst.append(left_half[0])
            left_half.remove(left_half[0])
        else:
            result_lst.append(right_half[0])
            right_half.remove(right_half[0])

    result_lst += right_half if len(left_half) == 0 else left_half
    print("Current result list value : ", result_lst)
    return result_lst

# Function for dividing an list and return final sorted list
def merge_sort(unsorted_list):
    if len(unsorted_list) <= 1:
        return unsorted_list

    # Find the middle point and divide it
    middle = len(unsorted_list) // 2
    left_list = unsorted_list[:middle]
    right_list = unsorted_list[middle:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
    return list(merge(left_list, right_list))


def main():
    lst = [8, 17, 3, 9]
    print("Initial Unsorted List:", lst)
    print("After Sorting:", merge_sort(lst))


if __name__ == "__main__":
    main()

Output:

Initial Unsorted List: [8, 17, 3, 9]After Sorting: [3, 8, 9, 17]

Flowchart For Merge Sort in Python

As you have read the code, Now it time for flowchart of Merge Sort.

Merge sort in Python flowchart

Now its, Time for short Youtube on Merge sort in Python code 🙂

Some Facts about Merge sort

Best Case Time ComplexityO(nLogn)
Average Case Time ComplexityO(nLogn)
Worst Case Time ComplexityO(nLogn)
Auxiliary SpaceO(n)
Algorithmic ParadigmDivide and Conquer
Sorting in PlaceNot in typical implementation
StabilityYes
Some Facts about Merge Sort

Merge Sort is more useful for sorting the linked list in O(nLogn) time than an array data structure.

This case becomes different mainly due to the difference in memory allocation of arrays and linked lists. In a linked list, nodes may not be adjacent in memory unlike to array. In the linked list, we can insert items in the middle in O(1) extra space and O(1) time, but the same condition doesn’t work fine on an array. Therefore merge operation of merge sort can be implemented without extra space for linked lists.

In the case of arrays, we can do random access as elements are contiguous in memory. Let us say we have an integer (4-byte) array A and let the address of A[0] be x then to access A[i], we can directly access the memory at (x + i*4). Unlike arrays, we can not do random access on the linked list. Quick Sort requires a lot of this kind of access. In the linked list to access i’th index, we have to travel each and every node from the head to i’th node as we don’t have a contiguous block of memory. Therefore, the overhead increases for quicksort. Merge sort accesses data sequentially and the need for random access is low.

Now our merge sort post comes to end. Hope you have enjoy it. If you do then please like and share my post in your friend circle.

0

Vishal Sharma

Currently pursuing Computer Science degree from G.B Pant Government Engineering college, New Delhi.

0 Comments

Leave a Reply