Mergesort algorithm in python

Mergesort algorithm is a divide and conquer algorithm. Its not efficient as Quicksort algorithm but in some cases Mergesort is better than Quicksort. For example if the data to be sorted is in a linked list then Quicksort is costly since in a linkedlist accessing random elements is costly and in Quicksort we have to access data randomly.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n log n)
Best Case Performance	O (n log n )
Average Case Performance	O(n log n)
Worst Case space Complexity		O (n)

	def merge(arr, start , end):
	if (start >= end):
	return
	mid = (end+start)//2
	merge(arr, start, mid)
	merge(arr, mid+1, end)
	left = start
	right = mid+1
	aux = []
	while( left<=mid and right<=end):
	if (arr[left] <= arr[right]):
	aux.append(arr[left])
	left += 1
	elif(arr[right] <= arr[left]):
	aux.append(arr[right])
	right += 1
	while (left <= mid):
	aux.append(arr[left])
	left += 1
	while (right <= end) :
	aux.append(arr[right])
	right += 1
	arr[start: end+1] = aux
	def merge_sort(arr):
	"""
	Args:
	arr(list_int32)
	Returns:
	list_int32
	"""
	# Write your code here.
	merge(arr, 0, len(arr)-1)
	return arr

view raw merge_sort.py hosted with ❤ by GitHub

	def mergeSort(alist):
	print("Splitting ",alist)
	if len(alist)>1:
	mid = len(alist)//2
	lefthalf = alist[:mid]
	righthalf = alist[mid:]
	mergeSort(lefthalf)
	mergeSort(righthalf)
	i=0
	j=0
	k=0
	while i<len(lefthalf) and j<len(righthalf):
	if lefthalf[i]<=righthalf[j]:
	alist[k]=lefthalf[i]
	i=i+1
	else:
	alist[k]=righthalf[j]
	j=j+1
	k=k+1
	while i<len(lefthalf):
	alist[k]=lefthalf[i]
	i=i+1
	k=k+1
	while j<len(righthalf):
	alist[k]=righthalf[j]
	j=j+1
	k=k+1
	print("Merging ",alist)
	alist = [54,26,93,17,77,31,44,55,20]
	mergeSort(alist)
	print(alist)

view raw MerSort.py hosted with ❤ by GitHub