def mergeSort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves
mergeSort(L) # Sorting the first half
mergeSort(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
def printList(arr):
for i in range(len(arr)):
print(arr[i], end = " ")
print()
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
print("Given array is", end = "\n")
printList(arr)
mergeSort(arr)
print("Sorted array is: ", end = "\n")
printList(arr)
What is the point of using mergeSort(L)
and mergeSort(R)
in the above code as even you remove this recursion, we can get the sorted list. Then why is this necessary? The above code is directly taken from geeks for geeks and also I have seen such recursions in merge sort in many other places as well. What's the point of using it.
And another question is: how can mergeSort(L)
or even mergeSort(R)
returns anything without any return
statement as it simply fails and returns nothing when length of arr
is < 1.
mergesort
function sorts the list in-place. I.e. it modifies the original list you pass. And Please learn more about merge sort and sorting in general.