/* * C Program sorts the numbers in ascending order using merge sort (merge_sort.c) */ /* #include #define MAXSIZE 1000 void array_print(char *s, int heap[], int no) { int i; printf("%s ", s); for (i = 0; i < no; i++) printf("%d ", heap[i]); printf("\n"); } void merge_sort(int list[], int low, int mid, int high) { int temp_index, right_index, left_index, i, temp[MAXSIZE]; temp_index = low; // index for temp array left_index = low; // left element's index of left part right_index = mid + 1; // left element's index of right part while ((left_index <= mid) && (right_index <= high)) { if (list[left_index] <= list[right_index]) { // in order temp[temp_index] = list[left_index]; // save smaller element in temp[temp_index] left_index++; // next left_index } else { // wrong order temp[temp_index] = list[right_index]; // save smaller element in temp[temp_index] right_index++; // next right_index } temp_index++; // next temp_index } // one of the two parts finished if (left_index > mid) { // left part finished for (i = right_index; i <= high; i++) { temp[temp_index] = list[i]; // copy rest of right part to temp temp_index++; } } else { // right part finished for (i = left_index; i <= mid; i++) { temp[temp_index] = list[i]; // copy rest of left part to temp temp_index++; } } for (i = low; i <= high; i++) { // for all elements list[i] = temp[i]; // copy temp back to list } } void partition(int list[], int low, int high) { int mid; if (low < high) { mid = (low + high) / 2; partition(list, low, mid); // recursively divide left part partition(list, mid+1, high); // recursively divide right part merge_sort(list, low, mid, high); // merge } } int main() { int array[MAXSIZE]; int i, num; printf("enter the number of elements n = "); scanf("%d", &num); printf("enter %d elements one by one\n", num); for (i = 0; i < num; i++) { scanf("%d", &array[i]); } array_print("\nthe original array is", array, num); partition(array, 0, num - 1); array_print("the sorted array is", array, num); return 0; } */ .text array_print: addiu $sp,$sp,-32 sw $31,28($sp) sw $fp,24($sp) move $fp,$sp sw $4,32($fp) sw $5,36($fp) sw $6,40($fp) lui $2,%hi($LC0) addiu $4,$2,%lo($LC0) lw $5,32($fp) jal printf nop sw $0,16($fp) j $L2 nop $L3: lw $2,16($fp) nop sll $2,$2,2 lw $3,36($fp) nop addu $2,$3,$2 lw $3,0($2) lui $2,%hi($LC1) addiu $4,$2,%lo($LC1) move $5,$3 jal printf nop lw $2,16($fp) nop addiu $2,$2,1 sw $2,16($fp) $L2: lw $3,16($fp) lw $2,40($fp) nop slt $2,$3,$2 bne $2,$0,$L3 nop li $4,10 jal putchar nop move $sp,$fp lw $31,28($sp) lw $fp,24($sp) addiu $sp,$sp,32 j $31 nop merge_sort: addiu $sp,$sp,-4024 sw $fp,4020($sp) move $fp,$sp sw $4,4024($fp) sw $5,4028($fp) sw $6,4032($fp) sw $7,4036($fp) lw $2,4028($fp) nop sw $2,0($fp) lw $2,4028($fp) nop sw $2,8($fp) lw $2,4032($fp) nop addiu $2,$2,1 sw $2,4($fp) j $L5 nop $L9: lw $2,8($fp) nop sll $2,$2,2 lw $3,4024($fp) nop addu $2,$3,$2 lw $3,0($2) lw $2,4($fp) nop sll $2,$2,2 lw $4,4024($fp) nop addu $2,$4,$2 lw $2,0($2) nop slt $2,$2,$3 bne $2,$0,$L6 nop lw $2,8($fp) nop sll $2,$2,2 lw $3,4024($fp) nop addu $2,$3,$2 lw $3,0($2) lw $2,0($fp) nop sll $2,$2,2 addu $2,$fp,$2 sw $3,16($2) lw $2,8($fp) nop addiu $2,$2,1 sw $2,8($fp) j $L7 nop $L6: lw $2,4($fp) nop sll $2,$2,2 lw $3,4024($fp) nop addu $2,$3,$2 lw $3,0($2) lw $2,0($fp) nop sll $2,$2,2 addu $2,$fp,$2 sw $3,16($2) lw $2,4($fp) nop addiu $2,$2,1 sw $2,4($fp) $L7: lw $2,0($fp) nop addiu $2,$2,1 sw $2,0($fp) $L5: lw $3,8($fp) lw $2,4032($fp) nop slt $2,$2,$3 bne $2,$0,$L8 nop lw $3,4($fp) lw $2,4036($fp) nop slt $2,$2,$3 beq $2,$0,$L9 nop $L8: lw $3,8($fp) lw $2,4032($fp) nop slt $2,$2,$3 beq $2,$0,$L10 nop lw $2,4($fp) nop sw $2,12($fp) j $L11 nop $L12: lw $2,12($fp) nop sll $2,$2,2 lw $3,4024($fp) nop addu $2,$3,$2 lw $3,0($2) lw $2,0($fp) nop sll $2,$2,2 addu $2,$fp,$2 sw $3,16($2) lw $2,0($fp) nop addiu $2,$2,1 sw $2,0($fp) lw $2,12($fp) nop addiu $2,$2,1 sw $2,12($fp) $L11: lw $3,12($fp) lw $2,4036($fp) nop slt $2,$2,$3 beq $2,$0,$L12 nop j $L13 nop $L10: lw $2,8($fp) nop sw $2,12($fp) j $L14 nop $L15: lw $2,12($fp) nop sll $2,$2,2 lw $3,4024($fp) nop addu $2,$3,$2 lw $3,0($2) lw $2,0($fp) nop sll $2,$2,2 addu $2,$fp,$2 sw $3,16($2) lw $2,0($fp) nop addiu $2,$2,1 sw $2,0($fp) lw $2,12($fp) nop addiu $2,$2,1 sw $2,12($fp) $L14: lw $3,12($fp) lw $2,4032($fp) nop slt $2,$2,$3 beq $2,$0,$L15 nop $L13: lw $2,4028($fp) nop sw $2,12($fp) j $L16 nop $L17: lw $2,12($fp) nop sll $2,$2,2 lw $3,4024($fp) nop addu $3,$3,$2 lw $2,12($fp) nop sll $2,$2,2 addu $2,$fp,$2 lw $2,16($2) nop sw $2,0($3) lw $2,12($fp) nop addiu $2,$2,1 sw $2,12($fp) $L16: lw $3,12($fp) lw $2,4036($fp) nop slt $2,$2,$3 beq $2,$0,$L17 nop move $sp,$fp lw $fp,4020($sp) addiu $sp,$sp,4024 j $31 nop partition: addiu $sp,$sp,-32 sw $31,28($sp) sw $fp,24($sp) move $fp,$sp sw $4,32($fp) sw $5,36($fp) sw $6,40($fp) lw $3,36($fp) lw $2,40($fp) nop slt $2,$3,$2 beq $2,$0,$L18 nop lw $3,36($fp) lw $2,40($fp) nop addu $2,$3,$2 srl $3,$2,31 addu $2,$3,$2 sra $2,$2,1 sw $2,16($fp) lw $4,32($fp) lw $5,36($fp) lw $6,16($fp) jal partition nop lw $2,16($fp) nop addiu $2,$2,1 lw $4,32($fp) move $5,$2 lw $6,40($fp) jal partition nop lw $4,32($fp) lw $5,36($fp) lw $6,16($fp) lw $7,40($fp) jal merge_sort nop $L18: move $sp,$fp lw $31,28($sp) lw $fp,24($sp) addiu $sp,$sp,32 j $31 nop main: addiu $sp,$sp,-4032 sw $31,4028($sp) sw $fp,4024($sp) move $fp,$sp lui $2,%hi($LC2) addiu $4,$2,%lo($LC2) jal printf nop addiu $3,$fp,4020 lui $2,%hi($LC3) addiu $4,$2,%lo($LC3) move $5,$3 jal scanf nop lw $3,4020($fp) lui $2,%hi($LC4) addiu $4,$2,%lo($LC4) move $5,$3 jal printf nop sw $0,16($fp) j $L21 nop $L22: addiu $3,$fp,20 lw $2,16($fp) nop sll $2,$2,2 addu $3,$3,$2 lui $2,%hi($LC3) addiu $4,$2,%lo($LC3) move $5,$3 jal scanf nop lw $2,16($fp) nop addiu $2,$2,1 sw $2,16($fp) $L21: lw $2,4020($fp) lw $3,16($fp) nop slt $2,$3,$2 bne $2,$0,$L22 nop lw $3,4020($fp) addiu $5,$fp,20 lui $2,%hi($LC5) addiu $4,$2,%lo($LC5) move $6,$3 jal array_print nop lw $2,4020($fp) nop addiu $2,$2,-1 addiu $3,$fp,20 move $4,$3 move $5,$0 move $6,$2 jal partition nop lw $3,4020($fp) addiu $5,$fp,20 lui $2,%hi($LC6) addiu $4,$2,%lo($LC6) move $6,$3 jal array_print nop move $2,$0 move $sp,$fp lw $31,4028($sp) lw $fp,4024($sp) addiu $sp,$sp,4032 j $31 nop .data $LC0: .ascii "%s \000" $LC1: .ascii "%d \000" $LC2: .ascii "enter the number of elements n = \000" $LC3: .ascii "%d\000" $LC4: .ascii "enter %d elements one by one\012\000" $LC5: .ascii "\012the original array is\000" $LC6: .ascii "the sorted array is\000" .end