 # Merge Sort in Python

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.

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 < right_half:
result_lst.append(left_half)
left_half.remove(left_half)
else:
result_lst.append(right_half)
right_half.remove(right_half)

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.