change C CODE to Merge sort IN MIPS assembly language

Merge sort is a comparison-based sorting algorithm. Its complexity is O(nlg(n)). Taking divide and conquer approaches, the algorithm divides an array to be sorted into two halves, sorts each half recursively, and then merges two sorted arrays. One of the main ideas behind merge sort is that it is easier to merge two sorted lists. The Wikipedia page (https://en.wikipedia.org/wiki/Merge_sort) has a nice description and some animations. The algorithm is also discussed in many algorithm books.

The C-like pseudocode is listed on the next page. It is sufficient for you to complete the lab. The interface of the function is:

void merge_sort(int p[], int n);

The function takes two arguments. The first argument p is the starting address of a word array. The second argument is the number of elements in the array. The function sorts the array into ascending order and places the sorted words back in the array p. The function does not return a value.

The main function in the skeleton code initializes a word array with random values, and then calls the merge sort function. You can change the number of words in the array by loading a different value in$s1. Remember to change it back to 1024 before submitting your code. The function check_arraychecks if array elements are in ascending order and if any data are corrupted. It is called twice in the main function: once before and once after the sorting. The program should output Not sorted and thenSorted. Your implementation must be recursive.

You only need to work on the merge_sort function. You may add other helper functions (e.g., copy array). Do not change the main function and other functions provided. To avoid name conflicts, all the labels you add in your code should start with L_, e.g., L_exit or l_exit.

Add brief comments in your code.

start code:

 .data #data segment .align 2 buffer: .space 4096 #allocate space for 1K words .align 2 name: .asciiz "merge sort" .text # Code segment .globl main # declare main to be global main: # specify the size of the array, must be less than 1024 la $s0, buffer # address of the buffer in $s0 li $s1, 1024 # number of elements in $s1 la $a0, name # load the address of "name" into $a0 li $v0, 4 # system call, type 4, print an string syscall # system call # call init_array() to initialize the array with random values move $a0, $s0 # use pseudoinstructions move $a1, $s1 jal init_array # check array move $a0, $s0 move $a1, $s1 jal check_array # call merge_sort function with proper arguments move $a0, $s0 move $a1, $s1 jal merge_sort # call merge_sort # check array move $a0, $s0 move $a1, $s1 jal check_array Exit: li $v0, 10 # System call, type 10, standard exit syscall # ...and call the OS ####START_OF_MERGE_SORT # void merge_sort(int p[], int n) # TODO merge_sort: jr $ra ####END_OF_MERGE_SORT ##### No need to change anything below # void init_array(int *p, int n), or # void init_array(int p[], int n) # use pseudorandom system calls in MARS init_array: #save parameters addi $t0, $a0, 0 addi $t1, $a1, 0 # set the seed li $a0, 0 li $a1, 3666 li $v0, 40 syscall lui $t2, 0x8000 # A while loop to put random numbers in the array j llinit_test llinit_loop: li $a0, 0 # syscall 41: rand() li $v0, 41 syscall # retry if the random number is 0x80000000 beq $a0, $t2, llinit_loop sw $a0, ($t0) # save the random value addi $t0, $t0, 4 # move to the next word addi $t1, $t1, -1 # n -- llinit_test: slti $at, $t1, 1 # n   Appendix: Pseudocode of the merge sort algorithm merge_sort(int P, int // Allocate space on stack and save registers // Let p3 be the starting address of a local array of n words if (n