class Solution {
    // using merge sort, recursive
    // time O(n * log n)
    // space O(n)
    public String[] sortPeople(String[] names, int[] heights) {
        mergeSort(names, heights, 0, names.length - 1);
        return names;
    }

    void mergeSort(String[] names, int[] heights, int first, int last) {
        if (first >= last) {
            return;
        }

        int mid = (first + last) / 2;
        mergeSort(names, heights, first, mid);
        mergeSort(names, heights, mid + 1, last);
        merge(names, heights, first, mid, last);
    }

    void merge(String[] names, int[] heights, int first, int mid, int last) {
        String[] tempNames = new String[names.length];
        int[] tempHeights = new int[heights.length];

        int first1 = first;
        int last1 = mid;
        int first2 = mid + 1;
        int last2 = last;

        // next available position in temporary array
        int index = first1;
        while ((first1 <= last1) && (first2 <= last2)) {
            if (heights[first1] < heights[first2]) {
                tempNames[index] = names[first2];
                tempHeights[index] = heights[first2];
                first2++;
            }
            else {
                tempNames[index] = names[first1];
                tempHeights[index] = heights[first1];
                first1++;
            }
            index++;
        }

        // finish off remaining ones
        while (first1 <= last1) {
            tempNames[index] = names[first1];
            tempHeights[index] = heights[first1];

            first1++;
            index++;
        }

        while (first2 <= last2) {
            tempNames[index] = names[first2];
            tempHeights[index] = heights[first2];

            first2++;
            index++;
        }

        // copy result back into original
        for (int i = first; i <= last; i++) {
            names[i] = tempNames[i];
            heights[i] = tempHeights[i];
        }
    }

    // using selection sort
    // time O(n^2)
    // space O(1)
    // public String[] sortPeople(String[] names, int[] heights) {
    //     for (int k = 0; k < names.length; k++) {
    //         // Find the tallest.
    //         int highestIndex = k;
    //         for (int i = k + 1; i < names.length; i++) {
    //             if (heights[i] > heights[highestIndex]) {
    //                 highestIndex = i;
    //             }
    //         }

    //         // Swap to place the subarray tallest in place.
    //         String temp = names[k];
    //         names[k] = names[highestIndex];
    //         names[highestIndex] = temp;
    //         int tempHeight = heights[k];
    //         heights[k] = heights[highestIndex];
    //         heights[highestIndex] = tempHeight;
    //     }

    //     return names;
    // }
}