.intel_syntax noprefix
.text
.global mergesort

// ; rdi, rsi, rdx, rcx, r8, r9
// ; void Merge(std::vector<Segment>& segments, int from, int middle, int to)
// ; extern void mergesort(int from, int to, const int *in, int *out);

mergesort:
    push rdx
    push rcx
    push r10
    push r12
    cmp r11d, 0
    je .fill_out
        .fill_out:
            mov r11d, 1
            mov r12d, [rdx]
            mov [rcx], r12d
            add rcx, 4
            add rdx, 4
            add r10d, 1
            cmp r10d, esi
            jl .fill_out

    pop r12
    pop r10
    pop rcx
    pop rdx
    push rsi // ; saving to
    push rdi //; saving from
    cmp edi, esi //; if from > to, return
        jg .return

    mov r12d, esi // writing in 12 register second argument a.k.a to
    add r12d, edi // add from
    mov eax, r12d
    mov r9d, 2
    div r9d // dividing whats in eax by 2
    mov esi, eax // wiritng eax in second argument
    call mergesort

    pop rdi
    pop rsi
    push rsi //  saving from
    push rdi // saving to
    mov edi, eax // writing middle in from
    add edi, 1 // adding 1 to get middle + 1
    call mergesort // calling mergesort with rest default arguments


    pop rdi
    pop rsi             //  returning values to their places
                        //; void Merge(std::vector<Segment>& segments, int from, int middle, int to)
                        //; extern void mergesort(int from, int to, const int *in, int *out);
    push rsi
    push rcx
    push rdi
    push rdx
    mov r14d, edi // writing from to 14-th register
    mov edi, ecx // writing in first argument pointer to out, where elems are already copied
    mov r13d, esi // writing in 13-th register second argument a.k.a to
    mov esi, r14d // writing in second argument 14-th register where is placed "from"
    mov ecx, r13d // writing to last argument 'to'
    mov edx, eax // writing in register that holds pointer to const middle, previously pushed him to stack
    call merge
    pop rdx
    pop rdi
    pop rcx
    pop rsi
    jmp .return
    .return:
    ret


merge:
    // ; rdx = middle, rsi = from, rcx = to
    mov r9d, esi // ; int i = from
    mov r10d, edx // ; int j = middle
    add r10d, 1 //; j += 1

    .while: // ; while(i <= middle && j <= to)
    cmp r9d, edx //;  r9 <= middle
        jle .fill_first //; if i(r9) <= rdx(middle) -> state to compare r10(j) and rcx(to)
        jg .fill_the_rest_with_second //; if r > middle, then we jump into state where we fill the rest with second part, if there are any left

    .fill_the_rest_with_second:
        cmp r10d, ecx // ; if j is greater than to, then we finish all this stuff
            jg .refill_array // ; refill with sorted elems
        push [rdi+r10*4] //; pushing segments[j] to stack
        add r10d, 1 //; j++
            jmp .fill_the_rest_with_second

    .fill_first: // ; here i(r9) <= middle
        cmp r10d, ecx //; if r10 <= rcx -> do the comparing while loop
            jle .fill_both //; -> state for comparing while loop
        push [rdi+r9*4] //; vector.push([segments[i]])
        add r9d, 1 //; i++
            jmp .while //; jump back to while

    .fill_both: //; we already checked that this is the case we need
        mov r8d, [rdi+r9*4]
        cmp r8d, [rdi+r10*4] //; if(arr[i] < arr[j]){ input in resullt array i-th the smaller element}
            jl .add_from_first //; push to stack the smaller if segments[i] < segments[j]
            jge .add_from_second //; else push segments[j]

    .add_from_first:
        push [rdi+r9*4] //; pushing segments[i]
        add r9d, 1 //; i++
        jmp .while //; jump back to while start

    .add_from_second:
        push [rdi+r10*4] //; pushing segments[j]
        add r10d, 1 //; j++
        jmp .while //; jumping back to while

    .refill_array:
        mov r9d, ecx //; i = to
        mov r10d, 0 // counter = 0
        loop:
            cmp r9d, esi // if i < from
                jl .end // end
            pop r10 // pop last pushed element
            mov [rdi+r9*4], r10d // place it from the back in out array
            sub r9d, 1
            jmp loop

        .end:
        ret