Question

python3:

Given a list of numbers in order order, return a new list sorted in non-decreasing order, and leave the original list unchanged.

function only

def mergeSort(inputArray):

#code here

a = [3,4,6,1,21,11,9,8]

b = mergeSort(a)

print('original array is: ', a)

print('sorted array is: ', b)

Answer 1

Code:

def mergeSortNew(arr):
if len(arr) >1:
mid = len(arr)//2 #Finding middle position of the array
L = arr[:mid] # Dividing the array elements equally into L and R
R = arr[mid:]
  
mergeSortNew(L) # running mergesort on first half of the array
mergeSortNew(R) # running mergesort on second half of the array
  
i = j = k = 0
  
# merging both the arrays
while i < len(L) and j < len(R):
if L[i] < R[j]: #copy least element first
arr[k] = L[i]
i+=1
else:
arr[k] = R[j]
j+=1
k+=1
  
# adding left over elements
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 mergeSort(ar):
res = []
res = res + ar
mergeSortNew(res)
return res
  
a = [3, 4, 6, 1, 21, 11, 9, 8]
b = mergeSort(a)
print('Original array is:', a)
print('sorted array is:', b)

Image version of code:

Output: