AS_1

#include <iostream>
#include <vector>
using namespace std;

int IsLargeApples(int i, int j); // function to compare sizes of apples

void mergeSort(vector<int>& A, vector<int>& S, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(A, S, left, mid);
    mergeSort(A, S, mid + 1, right);
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (IsLargeApples(A[S[i]], A[S[j]]) == -1) {
            temp[k++] = S[i++];
        } else {
            temp[k++] = S[j++];
        }
    }
    while (i <= mid) temp[k++] = S[i++];
    while (j <= right) temp[k++] = S[j++];
    for (int p = 0; p < k; p++) {
        S[left + p] = temp[p];
    }
}

vector<int> sortApples(vector<int>& A) {
    int n = A.size();
    vector<int> S(n);
    for (int i = 0; i < n; i++) {
        S[i] = i; // initialize S with indices of A
    }
    mergeSort(A, S, 0, n - 1);
    return S;
}

int main() {
    vector<int> A = {5, 2, 7, 3, 9, 1, 8, 6, 4};
    vector<int> S = sortApples(A);
    cout << "Sorted indices of apples: ";
    for (int i = 0; i < S.size(); i++) {
        cout << S[i] << " ";
    }
    cout << endl;
    return 0;
}