Project 1: Merge Sort

Objective:

In this project, you are expected to implement a merge sort algorithm in MIPS assembly language. A C++ implementation for merge sort is as follows.

int c[100]; //c[100] is a global array

mergesort(int a[], int low, int high){

int mid;

if (low < high) { mid=(low+high)/2;

mergesort(a,low,mid);

mergesort(a,mid+1,high);

merge(a,low,high,mid); }

return; }

void merge(int a[], int low, int high, int mid){

int i, j, k;

i = low;

k = low;

j = mid + 1;

while (i <= mid && j <= high){

if (a[i] < a[j]){

c[k] = a[i];

k++;

i++; }

else{

c[k] = a[j];

k++;

j++; } }

while (i <= mid){

c[k] = a[i];

k++;

i++; }

while (j <= high){

c[k] = a[j];

k++;

j++; }

for (i = low; i < k; i++){

a[i] = c[i]; }

}

Problem 1:

Consider the array [1,4,7,10,25,3,5,13,17,21]. The first and second halves of this array are both already sorted. In this case, the merge sort over this array is reduced to the merge of two sorted arrays: [1,4,7,10,25] and [3,5,13,17,21]. Implement the merge function (from the C++ code above) in assembly to sort this array.

Problem 2:

Given an array [56,3,46,47,34,12,1,5,10,8,33,25,29,31,50,43], implement the complete merge sort algorithm to sort this array.

Requirements:

1. You are required to implement merge sort in a separate procedures instead of in the main function.

2. The algorithm of your assembly program should be exact the same as the one of this C++ implementation.

3. You are required to implement the MIPS program in SPIM simulator.

4. Your program should be able to display the sorted array as the output. Please refer to SPIM syscall documentation on Blackboard to see how to display messages on screen.

Hints:

1. The code snippet below demonstrates how to define a single variable, an initialized array and an empty array in the .text segment.

# Define a variable, whose name is Var, type is .word and initial value is 12 Var .word 12

# Define an array, whose name is Array.

# The type of each array element is .word.

# The array is initialized to hold 5 elements: 3, 4, 6, 10, 2 Array .word 3,4,6,10,2

# Define an array, whose name is Array.

# The type of each array element is .word.

# The array has 16 elements, each of which is initialized to be 0. Array .word 0:16