In MIPS programming language: Write a \"main\" program to perform merge-sorting

Question

In MIPS programming language: Write a "main" program to perform merge-sorting of a list of integers by calling "merge" repeatedly. For example, if the sorting program takes (6,5,9,1,7,0,-3,2) as input, it will produce a sorted list (-3,0,1,2,4,6,7,9).

The original unsorted list of integers should be received from the keyboard input. Your program should first ask for the user to input the number of integers in the original list, and then ask for inputting all the integers. The total number of integers to be sorted by this program should be a power of 2. This means, the program should work with a list of 2, 4, 8, 16, or 32 (...) integers (but your program needs only to handle up to 32 integers).

The final sorted list (in increasing order) should be stored in the data area, that starts with the label "list:". The sorted list should also be displayed on the screen (console).

You should not do this part by implementing a different sorting algorithm (e.g. quick sort). You will receive 0% if you do not make use of "merge", or if your sorted list is in decreasing order.

[HINTS]: The bottom-up approach of implementation without using recursion is to initially sort the smallest possible sub-lists, and then merge every two neighboring sub-lists, until the whole list is merged and sorted. This non-recursive approach is more efficient in general, and is thus required for this assignment. [An alternative is to sort the list by dividing it into two sub-lists, recursively sorting the sub-lists, and then joining the sub-lists together to give the sorted list. But this recursive approach is not required in this assignment.]

Explanation / Answer

MIPS Code for merge sort using recursion .file 1 "" .section .mdebug.abi32 .previous .gnu_attribute 4, 1 .abicalls .globl arr .section .bss,"aw",@nobits .align 2 .type arr, @object .size arr, 80 arr: .space 80 .rdata .align 2 $LC0: .ascii "Enter the size of array" .align 2 $LC1: .ascii "%d" .align 2 $LC2: .ascii "Enter the elements:" .align 2 $LC3: .ascii "Sorted array: " .align 2 $LC4: .ascii "%d " .text .align 2 .globl main $LFB0 = . .set nomips16 .ent main .type main, @function main: .frame $fp,40,$31 # vars= 8, regs= 2/0, args= 16, gp= 8 .mask 0xc0000000,-4 .fmask 0x00000000,0 .set noreorder .cpload $25 .set nomacro addiu $sp,$sp,-40 $LCFI0: sw $31,36($sp) $LCFI1: sw $fp,32($sp) movz $31,$31,$0 $LCFI2: move $fp,$sp $LCFI3: .cprestore 16 lw $2,%got($LC0)($28) nop addiu $4,$2,%lo($LC0) lw $2,%call16(puts)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) addiu $2,$fp,28 lw $3,%got($LC1)($28) nop addiu $4,$3,%lo($LC1) move $5,$2 lw $2,%call16(scanf)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) nop lw $2,%got($LC2)($28) nop addiu $4,$2,%lo($LC2) lw $2,%call16(printf)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) sw $0,24($fp) b $L2 nop $L3: lw $2,24($fp) nop sll $3,$2,2 lw $2,%got(arr)($28) nop addu $2,$3,$2 lw $3,%got($LC1)($28) nop addiu $4,$3,%lo($LC1) move $5,$2 lw $2,%call16(scanf)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) lw $2,24($fp) nop addiu $2,$2,1 sw $2,24($fp) $L2: lw $2,28($fp) lw $3,24($fp) nop slt $2,$3,$2 andi $2,$2,0x00ff bne $2,$0,$L3 nop lw $2,28($fp) nop addiu $2,$2,-1 lw $4,%got(arr)($28) move $5,$0 move $6,$2 lw $2,%got(_Z10merge_sortPiii)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) nop lw $2,%got($LC3)($28) nop addiu $4,$2,%lo($LC3) lw $2,%call16(printf)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) sw $0,24($fp) b $L4 nop $L5: lw $2,24($fp) lw $3,%got(arr)($28) sll $2,$2,2 addu $2,$3,$2 lw $2,0($2) lw $3,%got($LC4)($28) nop addiu $4,$3,%lo($LC4) move $5,$2 lw $2,%call16(printf)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) lw $2,24($fp) nop addiu $2,$2,1 sw $2,24($fp) $L4: lw $2,28($fp) lw $3,24($fp) nop slt $2,$3,$2 andi $2,$2,0x00ff bne $2,$0,$L5 nop move $2,$0 move $sp,$fp lw $31,36($sp) lw $fp,32($sp) addiu $sp,$sp,40 j $31 nop .set macro .set reorder .end main $LFE0: .size main, .-main .align 2 .globl _Z10merge_sortPiii $LFB1 = . .set nomips16 .ent _Z10merge_sortPiii .type _Z10merge_sortPiii, @function _Z10merge_sortPiii: .frame $fp,40,$31 # vars= 8, regs= 2/0, args= 16, gp= 8 .mask 0xc0000000,-4 .fmask 0x00000000,0 .set noreorder .cpload $25 .set nomacro addiu $sp,$sp,-40 $LCFI4: sw $31,36($sp) $LCFI5: sw $fp,32($sp) movz $31,$31,$0 $LCFI6: move $fp,$sp $LCFI7: .cprestore 16 sw $4,40($fp) sw $5,44($fp) sw $6,48($fp) lw $3,44($fp) lw $2,48($fp) nop slt $2,$3,$2 beq $2,$0,$L8 nop lw $3,44($fp) lw $2,48($fp) nop addu $2,$3,$2 srl $3,$2,31 addu $2,$3,$2 sra $2,$2,1 sw $2,24($fp) lw $4,40($fp) lw $5,44($fp) lw $6,24($fp) lw $2,%got(_Z10merge_sortPiii)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) lw $2,24($fp) nop addiu $2,$2,1 lw $4,40($fp) move $5,$2 lw $6,48($fp) lw $2,%got(_Z10merge_sortPiii)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) lw $4,40($fp) lw $5,44($fp) lw $6,24($fp) lw $7,48($fp) lw $2,%got(_Z5mergePiiii)($28) nop move $25,$2 jalr $25 nop lw $28,16($fp) $L8: move $2,$0 move $sp,$fp lw $31,36($sp) lw $fp,32($sp) addiu $sp,$sp,40 j $31 nop .set macro .set reorder .end _Z10merge_sortPiii $LFE1: .size _Z10merge_sortPiii, .-_Z10merge_sortPiii .align 2 .globl _Z5mergePiiii $LFB2 = . .set nomips16 .ent _Z5mergePiiii .type _Z5mergePiiii, @function _Z5mergePiiii: .frame $fp,120,$31 # vars= 104, regs= 1/0, args= 0, gp= 8 .mask 0x40000000,-4 .fmask 0x00000000,0 .set noreorder .set nomacro addiu $sp,$sp,-120 $LCFI8: sw $fp,116($sp) $LCFI9: move $fp,$sp movz $31,$31,$0 $LCFI10: sw $4,120($fp) sw $5,124($fp) sw $6,128($fp) sw $7,132($fp) lw $3,128($fp) lw $2,124($fp) nop subu $2,$3,$2 addiu $2,$2,1 sw $2,24($fp) lw $3,132($fp) lw $2,128($fp) nop subu $2,$3,$2 sw $2,20($fp) sw $0,16($fp) b $L11 nop $L12: lw $2,16($fp) lw $4,124($fp) lw $3,16($fp) nop addu $3,$4,$3 sll $3,$3,2 lw $4,120($fp) nop addu $3,$4,$3 lw $3,0($3) sll $2,$2,2 addiu $4,$fp,8 addu $2,$4,$2 sw $3,20($2) lw $2,16($fp) nop addiu $2,$2,1 sw $2,16($fp) $L11: lw $3,16($fp) lw $2,24($fp) nop slt $2,$3,$2 andi $2,$2,0x00ff bne $2,$0,$L12 nop sw $0,12($fp) b $L13 nop $L14: lw $2,12($fp) lw $4,128($fp) lw $3,12($fp) nop addu $3,$4,$3 addiu $3,$3,1 sll $3,$3,2 lw $4,120($fp) nop addu $3,$4,$3 lw $3,0($3) sll $2,$2,2 addiu $4,$fp,8 addu $2,$4,$2 sw $3,60($2) lw $2,12($fp) nop addiu $2,$2,1 sw $2,12($fp) $L13: lw $3,12($fp) lw $2,20($fp) nop slt $2,$3,$2 andi $2,$2,0x00ff bne $2,$0,$L14 nop lw $2,16($fp) nop sll $2,$2,2 addiu $3,$fp,8 addu $2,$3,$2 li $3,9999 # 0x270f sw $3,20($2) lw $2,12($fp) nop sll $2,$2,2 addiu $3,$fp,8 addu $2,$3,$2 li $3,9999 # 0x270f sw $3,60($2) sw $0,16($fp) sw $0,12($fp) lw $2,124($fp) nop sw $2,8($fp) b $L15 nop $L18: lw $2,16($fp) nop sll $2,$2,2 addiu $3,$fp,8 addu $2,$3,$2 lw $3,20($2) lw $2,12($fp) nop sll $2,$2,2 addiu $4,$fp,8 addu $2,$4,$2 lw $2,60($2) nop slt $2,$2,$3 bne $2,$0,$L16 nop lw $2,8($fp) nop sll $2,$2,2 lw $3,120($fp) nop addu $3,$3,$2 lw $2,16($fp) nop sll $2,$2,2 addiu $4,$fp,8 addu $2,$4,$2 lw $2,20($2) nop sw $2,0($3) lw $2,16($fp) nop addiu $2,$2,1 sw $2,16($fp) b $L17 nop $L16: lw $2,8($fp) nop sll $2,$2,2 lw $3,120($fp) nop addu $3,$3,$2 lw $2,12($fp) nop sll $2,$2,2 addiu $4,$fp,8 addu $2,$4,$2 lw $2,60($2) nop sw $2,0($3) lw $2,12($fp) nop addiu $2,$2,1 sw $2,12($fp) $L17: lw $2,8($fp) nop addiu $2,$2,1 sw $2,8($fp) $L15: lw $3,8($fp) lw $2,132($fp) nop slt $2,$2,$3 xori $2,$2,0x1 andi $2,$2,0x00ff bne $2,$0,$L18 nop move $2,$0 move $sp,$fp lw $fp,116($sp) addiu $sp,$sp,120 j $31 nop .set macro .set reorder .end _Z5mergePiiii $LFE2: .size _Z5mergePiiii, .-_Z5mergePiiii .section .eh_frame,"aw",@progbits $Lframe1: .4byte $LECIE1-$LSCIE1 $LSCIE1: .4byte 0x0 .byte 0x1 .globl __gxx_personality_v0 .ascii "zP" .uleb128 0x1 .sleb128 -4 .byte 0x1f .uleb128 0x5 .byte 0x0 .4byte __gxx_personality_v0 .byte 0xc .uleb128 0x1d .uleb128 0x0 .align 2 $LECIE1: $LSFDE1: .4byte $LEFDE1-$LASFDE1 $LASFDE1: .4byte $LASFDE1-$Lframe1 .4byte $LFB0 .4byte $LFE0-$LFB0 .uleb128 0x0 .byte 0x4 .4byte $LCFI0-$LFB0 .byte 0xe .uleb128 0x28 .byte 0x4 .4byte $LCFI2-$LCFI0 .byte 0x11 .uleb128 0x1e .sleb128 2 .byte 0x11 .uleb128 0x1f .sleb128 1 .byte 0x4 .4byte $LCFI3-$LCFI2 .byte 0xd .uleb128 0x1e .align 2 $LEFDE1: $LSFDE3: .4byte $LEFDE3-$LASFDE3 $LASFDE3: .4byte $LASFDE3-$Lframe1 .4byte $LFB1 .4byte $LFE1-$LFB1 .uleb128 0x0 .byte 0x4 .4byte $LCFI4-$LFB1 .byte 0xe .uleb128 0x28 .byte 0x4 .4byte $LCFI6-$LCFI4 .byte 0x11 .uleb128 0x1e .sleb128 2 .byte 0x11 .uleb128 0x1f .sleb128 1 .byte 0x4 .4byte $LCFI7-$LCFI6 .byte 0xd .uleb128 0x1e .align 2 $LEFDE3: .ident "GCC: (Debian 4.4.5-8) 4.4.5"

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.