/*
 * C Program sorts the numbers in ascending order using merge sort (merge_sort.c)
 */
/*
#include <stdio.h>
#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:
    addi  sp,sp,-48
    sw    ra,44(sp)
    sw    s0,40(sp)
    addi  s0,sp,48
    sw    a0,-36(s0)
    sw    a1,-40(s0)
    sw    a2,-44(s0)
    lw    a1,-36(s0)
    lui   a5,%hi(.LC0)
    addi  a0,a5,%lo(.LC0)
    call  printf
    sw    zero,-20(s0)
    j    .L2
.L3:
    lw    a5,-20(s0)
    slli  a5,a5,2
    lw    a4,-40(s0)
    add   a5,a4,a5
    lw    a5,0(a5)
    mv    a1,a5
    lui   a5,%hi(.LC1)
    addi  a0,a5,%lo(.LC1)
    call  printf
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
.L2:
    lw    a4,-20(s0)
    lw    a5,-44(s0)
    blt   a4,a5,.L3
    li    a0,10
    call  putchar
    nop
    lw    ra,44(sp)
    lw    s0,40(sp)
    addi  sp,sp,48
    jr    ra
merge_sort:
    addi  sp,sp,-2032
    sw    s0,2028(sp)
    addi  s0,sp,2032
    addi  sp,sp,-2016
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    sw    a0,76(a5)
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    sw    a1,72(a5)
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    sw    a2,68(a5)
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    sw    a3,64(a5)
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,72(a5)
    sw    a5,-20(s0)
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,72(a5)
    sw    a5,-28(s0)
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,68(a5)
    addi  a5,a5,1
    sw    a5,-24(s0)
    j    .L5
.L9:
    lw    a5,-28(s0)
    slli  a5,a5,2
    li    a4,-4096
    addi  a3,s0,-16
    add   a4,a3,a4
    lw    a4,76(a4)
    add   a5,a4,a5
    lw    a4,0(a5)
    lw    a5,-24(s0)
    slli  a5,a5,2
    li    a3,-4096
    addi  a2,s0,-16
    add   a3,a2,a3
    lw    a3,76(a3)
    add   a5,a3,a5
    lw    a5,0(a5)
    bgt   a4,a5,.L6
    lw    a5,-28(s0)
    slli  a5,a5,2
    li    a4,-4096
    addi  a3,s0,-16
    add   a4,a3,a4
    lw    a4,76(a4)
    add   a5,a4,a5
    lw    a4,0(a5)
    li    a5,-4096
    addi  a3,s0,-16
    add   a3,a3,a5
    lw    a5,-20(s0)
    slli  a5,a5,2
    add   a5,a3,a5
    sw    a4,80(a5)
    lw    a5,-28(s0)
    addi  a5,a5,1
    sw    a5,-28(s0)
    j    .L7
.L6:
    lw    a5,-24(s0)
    slli  a5,a5,2
    li    a4,-4096
    addi  a3,s0,-16
    add   a4,a3,a4
    lw    a4,76(a4)
    add   a5,a4,a5
    lw    a4,0(a5)
    li    a5,-4096
    addi  a3,s0,-16
    add   a3,a3,a5
    lw    a5,-20(s0)
    slli  a5,a5,2
    add   a5,a3,a5
    sw    a4,80(a5)
    lw    a5,-24(s0)
    addi  a5,a5,1
    sw    a5,-24(s0)
.L7:
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
.L5:
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,-28(s0)
    lw    a5,68(a5)
    bgt   a4,a5,.L8
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,-24(s0)
    lw    a5,64(a5)
    ble   a4,a5,.L9
.L8:
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,-28(s0)
    lw    a5,68(a5)
    ble   a4,a5,.L10
    lw    a5,-24(s0)
    sw    a5,-32(s0)
    j    .L11
.L12:
    lw    a5,-32(s0)
    slli  a5,a5,2
    li    a4,-4096
    addi  a3,s0,-16
    add   a4,a3,a4
    lw    a4,76(a4)
    add   a5,a4,a5
    lw    a4,0(a5)
    li    a5,-4096
    addi  a3,s0,-16
    add   a3,a3,a5
    lw    a5,-20(s0)
    slli  a5,a5,2
    add   a5,a3,a5
    sw    a4,80(a5)
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
    lw    a5,-32(s0)
    addi  a5,a5,1
    sw    a5,-32(s0)
.L11:
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,-32(s0)
    lw    a5,64(a5)
    ble   a4,a5,.L12
    j    .L13
.L10:
    lw    a5,-28(s0)
    sw    a5,-32(s0)
    j    .L14
.L15:
    lw    a5,-32(s0)
    slli  a5,a5,2
    li    a4,-4096
    addi  a3,s0,-16
    add   a4,a3,a4
    lw    a4,76(a4)
    add   a5,a4,a5
    lw    a4,0(a5)
    li    a5,-4096
    addi  a3,s0,-16
    add   a3,a3,a5
    lw    a5,-20(s0)
    slli  a5,a5,2
    add   a5,a3,a5
    sw    a4,80(a5)
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
    lw    a5,-32(s0)
    addi  a5,a5,1
    sw    a5,-32(s0)
.L14:
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,-32(s0)
    lw    a5,68(a5)
    ble   a4,a5,.L15
.L13:
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,72(a5)
    sw    a5,-32(s0)
    j    .L16
.L17:
    lw    a5,-32(s0)
    slli  a5,a5,2
    li    a4,-4096
    addi  a3,s0,-16
    add   a4,a3,a4
    lw    a4,76(a4)
    add   a4,a4,a5
    li    a5,-4096
    addi  a3,s0,-16
    add   a3,a3,a5
    lw    a5,-32(s0)
    slli  a5,a5,2
    add   a5,a3,a5
    lw    a5,80(a5)
    sw    a5,0(a4)
    lw    a5,-32(s0)
    addi  a5,a5,1
    sw    a5,-32(s0)
.L16:
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,-32(s0)
    lw    a5,64(a5)
    ble   a4,a5,.L17
    nop
    addi  sp,sp,2016
    lw    s0,2028(sp)
    addi  sp,sp,2032
    jr    ra
partition:
    addi  sp,sp,-48
    sw    ra,44(sp)
    sw    s0,40(sp)
    addi  s0,sp,48
    sw    a0,-36(s0)
    sw    a1,-40(s0)
    sw    a2,-44(s0)
    lw    a4,-40(s0)
    lw    a5,-44(s0)
    bge   a4,a5,.L20
    lw    a4,-40(s0)
    lw    a5,-44(s0)
    add   a5,a4,a5
    srli    a4,a5,31
    add   a5,a4,a5
    srai    a5,a5,1
    sw    a5,-20(s0)
    lw    a2,-20(s0)
    lw    a1,-40(s0)
    lw    a0,-36(s0)
    call  partition
    lw    a5,-20(s0)
    addi  a5,a5,1
    lw    a2,-44(s0)
    mv    a1,a5
    lw    a0,-36(s0)
    call  partition
    lw    a3,-44(s0)
    lw    a2,-20(s0)
    lw    a1,-40(s0)
    lw    a0,-36(s0)
    call  merge_sort
.L20:
    nop
    lw    ra,44(sp)
    lw    s0,40(sp)
    addi  sp,sp,48
    jr    ra
main:
    addi  sp,sp,-2032
    sw    ra,2028(sp)
    sw    s0,2024(sp)
    addi  s0,sp,2032
    addi  sp,sp,-2000
    lui   a5,%hi(.LC2)
    addi  a0,a5,%lo(.LC2)
    call  printf
    li    a5,-4096
    addi  a5,a5,88
    addi  a4,s0,-16
    add   a5,a4,a5
    mv    a1,a5
    lui   a5,%hi(.LC3)
    addi  a0,a5,%lo(.LC3)
    call  scanf
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,88(a5)
    mv    a1,a5
    lui   a5,%hi(.LC4)
    addi  a0,a5,%lo(.LC4)
    call  printf
    sw    zero,-20(s0)
    j    .L22
.L23:
    li    a5,-4096
    addi  a5,a5,92
    addi  a4,s0,-16
    add   a4,a4,a5
    lw    a5,-20(s0)
    slli  a5,a5,2
    add   a5,a4,a5
    mv    a1,a5
    lui   a5,%hi(.LC3)
    addi  a0,a5,%lo(.LC3)
    call  scanf
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
.L22:
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,88(a5)
    lw    a4,-20(s0)
    blt   a4,a5,.L23
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,88(a5)
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a2,a4
    mv    a1,a5
    lui   a5,%hi(.LC5)
    addi  a0,a5,%lo(.LC5)
    call  array_print
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,88(a5)
    addi  a4,a5,-1
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a2,a4
    li    a1,0
    mv    a0,a5
    call  partition
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,88(a5)
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a2,a4
    mv    a1,a5
    lui   a5,%hi(.LC6)
    addi  a0,a5,%lo(.LC6)
    call  array_print
    li    a5,0
    mv    a0,a5
    addi  sp,sp,2000
    lw    ra,2028(sp)
    lw    s0,2024(sp)
    addi  sp,sp,2032
    jr    ra
.data
.LC0: .string "%s "
.LC1: .string "%d "
.LC2: .string "enter the number of elements n = "
.LC3: .string "%d"
.LC4: .string "enter %d elements one by one\n"
.LC5: .string "\nthe original array is"
.LC6: .string "the  sorted  array is"
.end