write insertion_sort function in aarch64 assembly language program
.section .rodata
    getnstr: .string "Enter a value of n: "
    .align 3
    origstr: .string "The original array is:\n"
    .align 3
    dupstr: .string "\n\nThe sorted duplicate array is:\n"
    .align 3
    dupstr2: .string "\n\nThe average of the duplicate array is: "
    intstr: .string "%d"
    .align 3
    tab10dintstr: .string "\t%10d"
    .align 3
    nlstr: .string "\n"
    .align 3


.section .bss
	n: .skip 4
	n16: .skip 4

.section .text
.global main
.type main, @function

main:
	stp x29, x30, [sp, #-16]! // main prolog
	
	// Generate a seed to be used by srand and set the seed for the random number generator
	mov x0, 0
	bl time
	bl srand
	
	// prompt the user to enter their TCU id number
	ldr x0, =getnstr
	bl printf
	ldr x0, =intstr
	ldr x1, =n
	bl scanf
	
	// Check if the TCU id number is even
	ldr x0, =n
	and x0, x0, #1
	cmp x0, #0
	beq even
	
	mov x0, #33
	ldr x1, =n
	str x0, [x1]
	b endgetnstr

even:
	mov x0, #42
	ldr x1, =n
	str x0, [x1]
	
endgetnstr:
	// compute next highest multiple of 16 that is bigger or equal to n
	adr x1, n
	ldr w1, [x1]
	sbfiz x1, x1, #2, #20
	add x1, x1, #0xf
	and x1, x1, #0xfffffffffffffff0
	adr x2, n16
	str w1, [x2]
	
	// create the storage for “n” integers (namely orig array) on stack pointer
	sub sp, sp, x1
	
	// call init_array
	mov x0, sp // move address of orig array to x0
	bl init_array
	
	// print orig array
	ldr x0, =origstr
	bl printf
	mov x0, sp
	bl print_array
	
	// create the storage for “n” integers (namely dup array) on stack pointer
	adr x2, n16
	ldr w2, [x2]
	sub sp, sp, x2
	
	// call copy_array
	mov x0, sp // address of dup array
	add x1, sp, x2 // address of orig array
	bl copy_array
	
	// call insertion_sort
	mov x0, sp // address of dup array
	bl insertion_sort
	
	// print dup array
	ldr x0, =dupstr
	bl printf
	mov x0, sp
	bl print_array
	ldr x0, =nlstr
	bl printf
	
	// call compute_average
	ldr x0, =dupstr2
	bl printf
	mov x0, sp // address of dup array
	bl compute_average
	
	// print out the average to standard output
	ldr x0, =intstr
	bl printf

	// restore storage for “n” integers (namely dup array) on stack pointer
	adr x1, n16
	ldr x1, [x1]
	add sp, sp, x1
	
	// restore storage for “n” integers (namely orig array) on stack pointer
	adr x1, n16
	ldr x1, [x1]
	add sp, sp, x1
	
	ldp x29, x30, [sp], #16 // main epilog
	mov x0, #0
	ret

.type init_array, @function
init_array:
	stp x29, x30, [sp, #-16]! //function prolog
	
	mov x19, #0 // loop counter
	ldr x20, =n
	ldr w20, [x20]
	mov x21, x0
	
loop1:
	cmp x19, x20
	bge endloop1
	
	// save random value to sp array
	bl rand
	and w0, w0, #255
	str w0, [x21, x19, lsl 2]
	
	add x19, x19, #1
	b loop1

endloop1:
	ldp x29, x30, [sp], #16 //function epilog
	ret

.type print_array, @function
print_array:
	stp x29, x30, [sp, #-16]! //function prolog
	
	mov x19, #0 // loop counter
	ldr x20, =n
	ldr w20, [x20]
	mov x21, x0
	
loop2:
	// restore x1, x2 from sp
	cmp x19, x20
	bge endloop2
	
	ldr x0, =tab10dintstr
	ldr w1, [x21, x19, lsl 2]
	bl printf
	
	add x19, x19, #1
	
	// check if x19 is multiple of 5, if yes print nlstr
	mov x22, #5
	sdiv x23, x19, x22
	mul x24, x23, x22
	cmp x24, x19
	bne continue_loop2
	ldr x0, =nlstr
	bl printf

continue_loop2:
	b loop2

endloop2:
	ldp x29, x30, [sp], #16 //function epilog
	ret


.type copy_array, @function
copy_array:
	stp x29, x30, [sp, #-16]! //function prolog
	
	mov x19, #0 // loop counter
	ldr x20, =n
	ldr w20, [x20]
	    mov x21, x1 // address of orig array
    mov x22, x0 // address of dup array
    
loop3:
    cmp x19, x20
    bge endloop3
    
    ldr w23, [x21, x19, lsl 2] // load value from orig array
    str w23, [x22, x19, lsl 2] // store value to dup array
    
    add x19, x19, #1
    b loop3
    
endloop3:
	ldp x29, x30, [sp], #16 //function epilog
	ret

.type compute_average, @function
compute_average:
	stp x29, x30, [sp, #-16]! //function prolog
	
	mov x19, #0 // loop counter
	ldr x20, =n
	ldr w20, [x20]
	mov x21, x0
	mov x22, #0 // initialize sum to 0

loop4:
    // restore x1, x2 from sp
    cmp x19, x20
    bge endloop4

    // add current element to sum
    ldr w0, [x21, x19, lsl 2]
    add x22, x22, x0

    add x19, x19, #1
    b loop4

endloop4:
	udiv x1, x22, x20
	ldp x29, x30, [sp], #16 //function epilog
	ret



.type insertion_sort, @function
insertion_sort:
    stp x29, x30, [sp, #-16]!  // function prolog
    
    mov x19, #0 // loop counter
	ldr x20, =n
	ldr w20, [x20]
	
	mov x21, x0 // address of dup array
    
    ldp x29, x30, [sp], #16  // function epilog
    ret