Merge sort

Merge sort is a divide and conquer algorithm. It is a fast, general purpose sorting algorithm.

Time complexity:

Average case : O(n log n)

Best case : O(n log n)

Worst case : O(n log n)

Worst case space complexity : O(n)

It works as follows :

  • If the length of the list is 0 or 1, it is considered as sorted.

  • The unsorted list is divided into two lists of approximately the same size.

  • Each list (left and right) is sorted recursively by re-applying the merge sort algorithm.

  • Once both the left and right lists are sorted they are merged to produce a sorted list

Implementation in Python :

def mergesort(list):
	if len(list) < 2:
		return list
	
	mid = int(len(list)/2)

	left = mergesort(list[:mid])
	right = mergesort(list[mid:])

	return merge(left, right)

def merge(left, right):
	result = list()
	il = 0
	ir = 0

	for ix in range(len(left) + len(right)):

		if il < len(left) and ir < len(right):
			if left[il] <= right[ir]:
				result.append(left[il])
				il += 1
			else:
				result.append(right[ir])
				ir += 1
		elif ir >= len(right):
			result.append(left[il])
			il += 1
		else:
			result.append(right[ir])
			ir += 1
	
	return result

if __name__ == "__main__":
    print(mergesort([3,2,1,4,-1,-2,0]))

Output:

[-2, -1, 0, 1, 2, 3, 4]

Links: