Sort the People

1class Solution {
2    // using merge sort, recursive
3    // time O(n * log n)
4    // space O(n)
5    public String[] sortPeople(String[] names, int[] heights) {
6        mergeSort(names, heights, 0, names.length - 1);
7        return names;
8    }
9
10    void mergeSort(String[] names, int[] heights, int first, int last) {
11        if (first >= last) {
12            return;
13        }
14
15        int mid = (first + last) / 2;
16        mergeSort(names, heights, first, mid);
17        mergeSort(names, heights, mid + 1, last);
18        merge(names, heights, first, mid, last);
19    }
20
21    void merge(String[] names, int[] heights, int first, int mid, int last) {
22        String[] tempNames = new String[names.length];
23        int[] tempHeights = new int[heights.length];
24
25        int first1 = first;
26        int last1 = mid;
27        int first2 = mid + 1;
28        int last2 = last;
29
30        // next available position in temporary array
31        int index = first1;
32        while ((first1 <= last1) && (first2 <= last2)) {
33            if (heights[first1] < heights[first2]) {
34                tempNames[index] = names[first2];
35                tempHeights[index] = heights[first2];
36                first2++;
37            }
38            else {
39                tempNames[index] = names[first1];
40                tempHeights[index] = heights[first1];
41                first1++;
42            }
43            index++;
44        }
45
46        // finish off remaining ones
47        while (first1 <= last1) {
48            tempNames[index] = names[first1];
49            tempHeights[index] = heights[first1];
50
51            first1++;
52            index++;
53        }
54
55        while (first2 <= last2) {
56            tempNames[index] = names[first2];
57            tempHeights[index] = heights[first2];
58
59            first2++;
60            index++;
61        }
62
63        // copy result back into original
64        for (int i = first; i <= last; i++) {
65            names[i] = tempNames[i];
66            heights[i] = tempHeights[i];
67        }
68    }
69
70    // using selection sort
71    // time O(n^2)
72    // space O(1)
73    // public String[] sortPeople(String[] names, int[] heights) {
74    //     for (int k = 0; k < names.length; k++) {
75    //         // Find the tallest.
76    //         int highestIndex = k;
77    //         for (int i = k + 1; i < names.length; i++) {
78    //             if (heights[i] > heights[highestIndex]) {
79    //                 highestIndex = i;
80    //             }
81    //         }
82
83    //         // Swap to place the subarray tallest in place.
84    //         String temp = names[k];
85    //         names[k] = names[highestIndex];
86    //         names[highestIndex] = temp;
87    //         int tempHeight = heights[k];
88    //         heights[k] = heights[highestIndex];
89    //         heights[highestIndex] = tempHeight;
90    //     }
91
92    //     return names;
93    // }
94}