Question

Please answer this multi-part question. Thank you!

For this assignment you must write the following functions in Scheme:

4 Write a recursive function called mergesort that sorts a list by doing the following:
(a) Use split to split the list into two roughly equal-sized partitions.
(b) Recursively sort both partitions.
(c) Use merge to merge the sorted partitions together.
Once again you will need two base cases, one for the empty list and the other for a single-element list.
> (mergesort '())

()

> (mergesort '(9))

(9)

> (mergesort '(8 6 7 5 3 0 9))

(0 3 5 6 7 8 9)

Answer 1

#include<iostream>
using namespace std;

void merge_partition(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r)    // base condition
 {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge_partition(arr, l, m, r);
    }
}

int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];

    mergeSort(arr, 0, n-1);

  for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";

   return 0;
}

PS:If this answer is helpful for you then please give an upvote.