Question

use python Write a function that will sort a given list using merge sort. You must use the merge sort algorithm (but may be recursive or iterative). The function will take a list as an input and return a sorted version of the list (you may assume it will be a list of integers). The method signature must be merge_sort(lst).

Answer 1

Merge sort algouthm.- esort Merge Carro] 18 If rol Find the middle point to divide the array into two halves I. - 2 middle om (ltr)/2 Call Mergesort for first half Call mergesort Carr,lim Call.Merge sort for second half obo call mergesort Larr, m+1,7) obiet 3 halves sorted 19 Merge the two Step 2 call merge cary, lim, nj si

Without start,end value arguments we cant do merge sorting...

# Mergesort using python

# Merges two subarrays of arr[].
# First half of the subarray is arr[l..m]
# Second half of the subarray is arr[m+1..r]
def merge(arrr,l,m,r):
   n1 = m-l+1
   n2 = r- m

   # create temp arrays
   L = [0] * (n1)
   R = [0] * (n2)

   # Copy data to temp arrays L[] and R[]
   for i in range(0 , n1):
       L[i] = arrr[l + i]

   for j in range(0 , n2):
       R[j] = arrr[m + 1 + j]

   # Merge the temp arrays back into arr[l..r]
   i = 0   # start index of first subarray
   j = 0   # start index of second subarray
   k = l   # start index of merged subarray

   while i < n1 and j < n2 :
   # if array L is minimum then copying that to new array
       if L[i] <= R[j]:
           arrr[k] = L[i]
           i += 1
       # if array R is minimum then copying that to new array
       else:
           arrr[k] = R[j]
           j += 1
       k += 1

   # Copy the remaining elements of L[], if there
   # are any
   while i < n1:
       arrr[k] = L[i]
       i += 1
       k += 1

   # Copy the remaining elements of R[], if there
   # are any
   while j < n2:
       arrr[k] = R[j]
       j += 1
       k += 1

# l is for left index and r is right index of the
# sub-array of arr to be sorted
def merge_sort(arrr,l,r):
if l<r:
       # Same as (l+r)//2, but avoids overflow for
       # large l and h
   m =(l+(r-1))//2
       # Sort first and second halves
   merge_sort(arrr,l,m)
   merge_sort(arrr,m+1,r)
   merge(arrr, l, m, r)

# Driver code to test above
lst = [12, 11, 13, 5, 6, 7]
n = len(lst)
print ("Given array is")
for i in range(n):
   print ("%d" %lst[i]),
merge_sort(lst,0,n-1)
print ("\n\nSorted array is")
for i in range(n):
   print ("%d" %lst[i]),

5 main.py 1 # Mergesort using python 2 3 # Merges two subarrays of arr[]. 4 # First half of the subarray is arr[l..m] # Second half of the subarray is arr[m+1..r] 6- def merge(arrr,l,m,r): 7 n1 m-1+1 8 n2 = rm 9 10 # create temp arrays 11 L = [0] * (nl) 12 R = [@] * (n2) 13 14 # Copy data to temp arrays L[] and R[] 15 for i in range(, n1): 16 L[i] = arrr[1 + i] 17 18 for j in range( , n2): 19 R[j] = arrr[m + 1 + j] 20 21 # Merge the temp arrays back into arr[L..r] 22 i = 0 # start index of first subarray 23 j = 0 # start index of second subarray 24 k = 1 # start index of merged subarray 25 26 while i < n1 and j < n2 : 27 # if array L is minimum then copying that to new array 28 if L[i] <= R[j]: 29 arrr[k] L[i] 30 i += 1 31 # if array R is minimum then copying that to new array 32 else: 33 arrr[k] = R[j] 34 j += 1 35 k += 1 36

37 # Copy the remaining elements of L[], if there 38 # are any 39 while i < n1: 40 arrr[k] L[i] 41 i += 1 42 k += 1 43 44 # Copy the remaining elements of R[], if there 45 # are any 46 while j < n2: 47 arrr[k] R[j] 48 j += 1 49 k += 1 50 51 # L is for Left index and ris right index of the 52 # sub-array of arr to be sorted 53 def merge_sort(arrr,1,r): 54 if l<r: 55 # Same as (L+r)//2, but avoids overflow for 56 # Large L and h 57 m =(1+(r-1))//2 58 # Sort first and second halves 59 merge_sort(arrr,1,m) 60 merge_sort(arrr,m+1,r) 61 merge(arrr, 1, m, r) 62 63 # Driver code to test above 64 lst [12, 11, 13, 5, 6, 7] 65 n = len(1st) 66 print ("Given array is") 67 for i in range(n): 68 print ("%d" %1st[i]), 69 merge_sort(1st,,n-1) 70 print ("\n\nSorted array is") 71- for i in range(n): 72 print ("%d" %1st[i]).

Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13