.global mergesort
    .global mergesort_
    .global merge
    .intel_syntax noprefix
    .text

merge:
    push ebp
    mov ebp, esp

    push eax
    push ebx
    push ecx
    push edx



    mov ecx, 0      /* i = 0 */
    mov edx, 0      /* j = 0  */

merge_stage:

    mov eax, [ebp + 12]     /* first array size */
    mov ebx, [ebp + 20]     /* second array size */

    cmp ecx, eax        /*  if (i < a.sz)  */
    jl second_check
    jmp full_first



second_check:
    cmp edx, ebx
    jl compare      /* if (j < b.sz ) */
    jmp full_second

compare:
    mov eax, [ebp + 8]          /* get a[i] */
    mov eax, [eax + 4 * ecx]
    mov ebx, [ebp + 16]
    mov ebx, [ebx + 4 * edx]        /* get b[j */

    mov edi, [ebp + 24]         /* *c   */
    cmp eax, ebx
    jl first_min        /* if (a[i] < b[j])  */
    jmp second_min


full_first:
    cmp edx, ebx
    jl continue_s           /* if (j < b.sz ) */
    jmp end

continue_s:
    mov eax, [ebp + 16]
    mov eax, [eax + 4 * edx]        /* get b[j]  */

    mov edi, [ebp + 24]


    mov esi, 4
    imul esi, ecx
    add edi, esi

    mov esi, 4
    imul esi, edx
    add edi, esi

    mov [edi], eax

    add edx, 1
    jmp full_first


full_second:
    cmp ecx, eax
    jl continue_f
    jmp end

continue_f:
    mov ebx, [ebp + 8]
    mov ebx, [ebx + 4 * ecx]        /* get a[i]  */
    mov edi, [ebp + 24]

    mov esi, 4
    imul esi, ecx
    add edi, esi

    mov esi, 4
    imul esi, edx
    add edi, esi
    mov [edi], ebx

    add ecx, 1
    jmp full_second

first_min:
    mov esi, 4
    imul esi, ecx
    add edi, esi

    mov esi, 4
    imul esi, edx
    add edi, esi

    mov [edi], eax
    add ecx, 1
    jmp merge_stage


second_min:
    mov esi, 4
    imul esi, ecx
    add edi, esi
    mov esi, 4
    imul esi, edx
    add edi, esi
    mov [edi], ebx
    add edx, 1
    jmp merge_stage

end:
    pop edx
    pop ecx
    pop ebx
    pop eax
    pop ebp
    ret


mergesort_:
    push ebp
    mov ebp, esp
    push ebx

    mov eax, [ebp + 12]
    sub eax, [ebp + 8]




    cmp eax, 2              /* eax = size */
    jl end_merge

    xor edx, edx
    mov ebx, 2

    idiv ebx

    add eax, [ebp + 8]
    push eax            /* eax = border */


    mov ebx, eax
    sub ebx, [ebp + 8]
    push ebx


    push [ebp + 20]
    push [ebp + 16]
    push eax
    push [ebp + 8]
    call mergesort_

    pop esi
    pop eax
    pop esi
    pop esi


    push [ebp + 20]
    push [ebp + 16]
    push [ebp + 12]
    push eax

    call mergesort_

    pop eax
    pop esi
    pop esi
    pop esi

    pop edx
    pop eax


    mov ebx, [ebp + 12]
    sub ebx, eax            /* ebx - b.sz */



    mov esi, 4
    imul esi, ebx
    sub esp, esi
    mov esi, 4

    imul esi, edx
    sub esp, esi

    push esp
    push ebx

    mov edi, [ebp + 20]
    mov esi, 4
    imul esi, eax
    add edi, esi

    push edi
    push edx

    mov edi, [ebp + 20]
    mov esi, 4
    imul esi, [ebp + 8]
    add edi, esi
    push edi


    call merge

    pop edx
    pop ecx
    pop ebx
    pop eax
    pop esp


    mov edx, [ebp + 20]
    mov esi, 0

    add eax, ecx    /* full size */

fill:
    mov ebx, [ebp + 8]
    cmp esi, eax
    jl copy
    jmp end_merge


copy:
    add ebx, esi
    mov ecx, [esp]
    mov [edx + 4 * ebx], ecx
    add esp, 4
    add esi, 1
    jmp fill



end_merge:
    pop ebx
    pop ebp
    ret


mergesort:
    push ebp
    mov ebp, esp
    push ebx

    mov eax, [ebp + 8]
    mov ebx, [ebp + 12]
    mov ecx, [ebp + 16]
    mov edx, [ebp + 20]

    mov esi, 0
    sub ebx, eax

while:
    cmp esi, ebx
    jl nfull
    jmp next_step

nfull:
    mov edi, eax
    add edi, esi
    mov edi, [ecx + 4 * edi]
    mov [edx + 4 * esi], edi
    add esi, 1
    jmp while

next_step:
    push [ebp + 20]
    push [ebp + 16]
    push ebx
    push 0

    call mergesort_

    pop eax
    pop eax
    pop eax
    pop eax

    pop ebx
    pop ebp
    ret



scanf_and_printf_format_ptr:
    .long scanf_and_printf_format

scanf_and_printf_format:
    .string "%d %d\n"