Merge Sort Algorithm in Python

Merge sort algorithm is based on the divide and conquer algorithm. Although this algorithm consumes more memory, this algorithm is widely used nowadays because of its less complexity.

Below are the few important things to consider while using this algorithm,

1. Merge sort is efficient to use when the data set is very large. If the array size is smaller, you can use quicksort.
2. Merge sort is a stable algorithm. It means that this sort preserves the sorting of the other dependent columns. Please refer to https://www.coursera.org/lecture/algorithms-part1/stability-pvvLZ for more information.
3. The time complexity is O(n logn) and the space complexity is O(n).
4. More suitable for the linked list than arrays.

Please find below the python coding for the merge sort algorithm:

def merge_sort(arr):
    arr_len = len(arr)
    if(arr_len > 1):
        mid = arr_len//2
        left_arr = arr[:mid]
        right_arr = arr[mid:]
        merge_sort(left_arr)
        merge_sort(right_arr)
        i = j = k = 0
        left_arr_len = len(left_arr)
        right_arr_len = len(right_arr)
        while(i<left_arr_len and j<right_arr_len):
            if(left_arr[i] < right_arr[j]):
                arr[k] = left_arr[i]
                i += 1
            else:
                arr[k] = right_arr[j]
                j += 1
            k += 1
        if(i < left_arr_len):
            arr[k:] = left_arr[i:]
        else:
            arr[k:] = right_arr[j:] 
        return arr
    return arr
arr = [2,4,5,6,2,4,5,6]
print(merge_sort(arr))
"test cases"
"empty list []"
"list with one element [1]"
"already sorted list [1,2,3,4,5]"
"reverse sorted list [7,6,5,4]"
"list with duplicate values [1,2,2,0,8,7]"

Happy Learning!