Sorting books

#include <bits/stdc++.h>

using namespace std;

int N;

int merge(vector<int> &A, int start, int mid, int end) {

    int output = 0;

    if (A[mid] <= A[mid+1]) {
        return output;
    }

    int m = mid;
    int start1 = start;
    int start2 = mid + 1;

    while (start1 <= m && start2 <= end) {

        if (A[start1] <= A[start2]) {
            start1 += 1;
        } else {

            int val = A[start2];
            int index = start2;

            while (index != start1) {
                output++;
                A[index] = A[index-1];
                index -= 1;
            }

            A[start1] = val;

            start1 += 1;
            m += 1;
            start2 += 1;
        }

    }

    return output;

}

int sort_between(vector<int> &A, int left, int right) {

    if (left < right) {
        int mid = left + (right - left)/2;
        int a = sort_between(A, left, mid);
        int b = sort_between(A, mid+1, right);
        int c = merge(A, left, mid, right);
        return a + b + c;
    }

    return 0;

}

int main() {

    int N;
    cin >> N;

    vector<int> A(N);
    for (int i = 0; i < N; i++)
        cin >> A[i];
    
    int o = sort_between(A, 0, A.size()-1);
    cout << o << endl;

    return 0;

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: TIME LIMIT EXCEEDED

Test 62

Verdict: TIME LIMIT EXCEEDED

Test 63

Verdict: TIME LIMIT EXCEEDED

Test 64

Verdict: TIME LIMIT EXCEEDED

Test 65

Verdict: TIME LIMIT EXCEEDED

Test 66

Verdict: TIME LIMIT EXCEEDED

Test 67

Verdict: TIME LIMIT EXCEEDED

Test 68

Verdict: TIME LIMIT EXCEEDED

Test 69

Verdict: TIME LIMIT EXCEEDED

Test 70

Verdict: TIME LIMIT EXCEEDED

Test 71

Verdict: ACCEPTED