Code must be in python. Exercise 1 [10 pts]. As discussed in class, merge sort i

Question

Code must be in python.

Exercise 1 [10 pts]. As discussed in class, merge sort is a recursive sorting algorithm that continually splits a list in half following the divide and conquer strategy. Once two halves are sorted, the fundamental operation "merge" is performed. Write the functions merge(listl, list2) [5 pts] and merge_sort(numList) [5 pts] to correctly sort a list of numbers. merge_sort is a recursive function that calls merge to return the final sorted list Remember: If the list is empty or has one item, it is sorted by definition Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list - EXAMPLES: >>>merge_sort ([12,35, 87,26,9,28,7]) 7, 9, 12, 26, 28, 35, 87 >>> merge ([12,26,35, 87, [7,9,28]) 7, 9, 12, 26, 28, 35, 87] >>> merge ([12,35], [26, 87]) 12, 26, 35, 871

Explanation / Answer

# p is the index of left most element

# r is the index of right most element

def merge_sort_util(list1 , p , r):

   

    if p < r:

        # get the index of middle element

        m = int( ( p + ( r - 1 ) ) / 2 )

       

        # sort the left subarray

        merge_sort_util(list1, p, m)

       

        # sort the right subarray

        merge_sort_util(list1, m + 1, r)

        # merge the two subarrays

        merge(list1, p, m, r)

# merge the two subarrays

def merge(list1, p, m, r):

    len1 = m - p + 1

    len2 = r - m

    # create temporary array with each element 0

    left = [0] * (len1)

    right = [0] * (len2)

    # Copy data to temp arrays left[] and right[]

    for i in range(0 , len1):

        left[i] = list1[p + i]

    for j in range(0 , len2):

        right[j] = list1[m + 1 + j]

    i = 0

    j = 0

    k = p

    while i < len1 and j < len2:

        if left[i] <= right[j]:

            list1[k] = left[i]

            i += 1

        else:

            list1[k] = right[j]

            j += 1

        k += 1

    # copy the remaining elements of left

    while i < len1:

        list1[k] = left[i]

        i += 1

        k += 1

    # copy the remaining elements of right

    while j < len2:

        list1[k] = right[j]

        j += 1

        k += 1

def merge_sort( list1 ):

    merge_sort_util( list1 , 0 , len(list1) - 1 )

   

    return list1

print(merge_sort([12 , 35 , 87 , 26 , 9 , 28 , 7]))

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.