{"id":182342,"date":"2025-01-13T16:52:11","date_gmt":"2025-01-13T16:52:11","guid":{"rendered":"https:\/\/learnexams.com\/blog\/?p=182342"},"modified":"2025-01-13T16:52:13","modified_gmt":"2025-01-13T16:52:13","slug":"write-a-mips-assembly-language-for-sorting-an-array-of-integers-using-non-recursive-bottom-up-merge-sort-algorithm","status":"publish","type":"post","link":"https:\/\/www.learnexams.com\/blog\/2025\/01\/13\/write-a-mips-assembly-language-for-sorting-an-array-of-integers-using-non-recursive-bottom-up-merge-sort-algorithm\/","title":{"rendered":"Write a MIPS assembly language for sorting an array of integers using non-recursive bottom-up merge sort algorithm"},"content":{"rendered":"\n

Write a MIPS assembly language for sorting an array of integers using non-recursive bottom-up merge sort algorithm. Your program should print the processed array after
each step of the merge sort.<\/p>\n\n\n\n

Bottom-up merge sort is a non-recursive variant of the merge sort, in which the array is sorted by a sequence of passes. During each pass, the array is divided into blocks of size m. (Initially, m1). Every two adjacent blocks are merged (as in normal merge sort), and the next pass is made with a twice larger value of m.<\/p>\n\n\n\n

Here is the pseudo code for bottom-up merge sort:<\/p>\n\n\n\n

Input: array a[l indexed from 0 to n-1.<\/p>\n\n\n\n

while m <- n=”” do=”” 1=”” 0=”” while=”” i=”” n-m=”” do=”” merge=”” subarrays=”” a[i.=”” .i+m-1]=”” and=”” a[i+m=”” ..=”” min(i+2*m-1,n-1)]=”” in-place=”” m=”” m2=””><\/p>\n\n\n\n

For example, if the input array is 14 27 13 11 49 63 17 9, your program should output the following:<\/p>\n\n\n\n

Input Array<\/p>\n\n\n\n

14 27 13 11 49 63 17 9<\/p>\n\n\n\n

After first Iteration<\/p>\n\n\n\n

14 27 11 13 49 63 9 17<\/p>\n\n\n\n

After second iteration<\/p>\n\n\n\n

11 13 14 27 9 17 49 63<\/p>\n\n\n\n

After third iteration<\/p>\n\n\n\n

9 11 13 14 17 27 49 63<\/p>\n\n\n\n

The Correct Answer and Explanation is :<\/strong><\/mark><\/p>\n\n\n\n

Implementing a non-recursive bottom-up merge sort in MIPS assembly involves sorting an array of integers through iterative merging of subarrays. In this approach, the array is divided into blocks of increasing size, and adjacent blocks are merged in each iteration. After each merge step, the program prints the current state of the array.<\/p>\n\n\n\n

MIPS Assembly Implementation:<\/strong><\/p>\n\n\n\n

.data\n    prompt: .asciiz \"Enter the number of elements: \"\n    newline: .asciiz \"\\n\"\n    array: .word 14, 27, 13, 11, 49, 63, 17, 9\n    array_size: .word 8\n\n.text\n    .globl main\n\nmain:\n    # Load the address of the array and its size\n    la $a0, array\n    lw $a1, array_size\n\n    # Print the initial array\n    li $v0, 4\n    la $a0, prompt\n    syscall\n\n    li $v0, 1\n    la $a0, array\n    lw $a1, array_size\n    syscall\n\n    # Bottom-up merge sort\n    li $t0, 1          # m = 1\n    li $t1, 0          # i = 0\n\nmerge_sort:\n    # Check if m >= n\n    lw $t2, array_size\n    bge $t0, $t2, end_sort\n\n    # Merge subarrays of size m\n    li $t1, 0          # i = 0\n\nmerge_loop:\n    # Calculate the end index of the first subarray\n    add $t3, $t1, $t0\n    bge $t3, $t2, merge_done\n\n    # Calculate the end index of the second subarray\n    add $t4, $t3, $t0\n    bge $t4, $t2, merge_done\n\n    # Merge the two subarrays\n    la $a0, array\n    add $a1, $a0, $t1\n    add $a2, $a0, $t3\n    add $a3, $a0, $t4\n    jal merge\n\n    # Update i\n    addi $t1, $t1, $t0\n    j merge_loop\n\nmerge_done:\n    # Print the array after this iteration\n    li $v0, 4\n    la $a0, newline\n    syscall\n\n    li $v0, 1\n    la $a0, array\n    lw $a1, array_size\n    syscall\n\n    # Double m\n    sll $t0, $t0, 1\n    j merge_sort\n\nend_sort:\n    # Exit the program\n    li $v0, 10\n    syscall\n\nmerge:\n    # Merge two sorted subarrays\n    # Arguments: $a0 = base address, $a1 = start of first subarray,\n    #            $a2 = start of second subarray, $a3 = end of second subarray\n    # Implementation of the merge operation\n    # ...\n    jr $ra<\/code><\/pre>\n\n\n\n
Explanation:<\/strong><\/p>\n\n\n\n
    \n
  1. Data Section:<\/strong><\/li>\n<\/ol>\n\n\n\n