Program 4: Shell Sort

It is assumed that, before your begin coding, you will already know about: Instructions: la, li, move, add, addi, div, sub, beq (be equal to), ble(be less than or equal to), blt (be less than), mflo, mfhi, j, jal, jr , and/or others. Pseudoinstructions: b. Other: The use of syscall for integer input from the keyboard. Also, the use of the $ai and $vi registers for passing arguments to a function and for returning its results.

Write a program in MIPS that:

(1) first asks user to input an array of integers. The end of the array is indicated by entering -999.

(2) prints out the array of integers in its original input order;

(3) uses shell sort to sort this set of integers and prints the sorted array. Shell sort should be implemented as a function in MIPS. The main program should call it whenever it needs to sort an array. The shell sort algorithm is shown in the following code.

/********************* Shell sort function ********************/

void shellSort(int numbers[], int array_size)

{

int i, j, increment, temp;

increment = 3;

while (increment > 0)

{

for (i=0; i < array_size; i++)

{

j = i;

temp = numbers[i];

while ((j >= increment) && (numbers[j-increment] > temp))

{

numbers[j] = numbers[j - increment];

j = j - increment;

}

numbers[j] = temp;

}

if (increment/2 != 0)

increment = increment/2;

else if (increment == 1)

increment = 0;

else

increment = 1;

}

}

/********************* End shell sort function *******************/