public class State {
public String name;
public String governor;
public State(String nameInput, String governorInput) {
name = nameInput;
governor = governorInput;
}
public String getName() {
return name;
}
public String getGovernor() {
return governor;
}
}
public class MergeSort {
public void toString(State[] states) {
String output = "";
for (int i = 0; i < states.length; i++) {
if (i == states.length - 1) {
output += states[i].getName() + "-" + states[i].getGovernor();
} else {
output += states[i].getName() + "-" + states[i].getGovernor() + ", ";
}
}
System.out.println(output);
}
public void sort(String arr[], int l, int r) {
// As long as the component is large enough to be divide, keeping running the functions
if (l < r) {
// Find midpoint of current component, and run functions on it
int m = l + (r - l) / 2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public void merge(String[] arr, int l, int m, int r) {
// Size of first half
int n1 = m - l + 1;
// Size of second half
int n2 = r - m;
// Left array
String[] L = new String[n1];
// Right array
String[] R = new String[n2];
for (int i = 0; i < n1; ++i) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[m + 1 + j];
}
int i = 0, j = 0;
// Initial index of main array
int k = l;
while (i < n1 && j < n2) {
// Use compareTo function to compare alphabetical standings of words. Merge sort takes place, as words with characters earlier
// in the alphabet are added to arr first
if (L[i].compareTo(R[j]) <= 0) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Add any remaining elements in the left array
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
//Add any remaining in the right array
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public void sort2(State arr[], int l, int r) {
// As long as the component is large enough to be divide, keeping running the functions
if (l < r) {
// Find midpoint of current component, and run functions on it
int m = l + (r - l) / 2;
sort2(arr, l, m);
sort2(arr, m + 1, r);
merge2(arr, l, m, r);
}
}
public void merge2(State[] arr, int l, int m, int r) {
// Size of first half
int n1 = m - l + 1;
// Size of second half
int n2 = r - m;
// Left array
State[] L = new State[n1];
// Right array
State[] R = new State[n2];
for (int i = 0; i < n1; ++i) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[m + 1 + j];
}
int i = 0, j = 0;
// Initial index of main array
int k = l;
while (i < n1 && j < n2) {
// Use compareTo function to compare alphabetical standings of words. Merge sort takes place, as words with characters earlier
// in the alphabet are added to arr first
if (L[i].getName().compareTo(R[j].getName()) <= 0) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Add any remaining elements in the left array
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
//Add any remaining in the right array
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
String[] words = {"apple", "cantelope" , "egg", "banana", "blueberry", "kiwi"};
System.out.println("Unsorted array:");
for (String item : words) {
System.out.print(item + " ");
}
System.out.println("");
MergeSort myObj = new MergeSort();
myObj.sort(words, 0, words.length - 1);
System.out.println("Sorted array:");
for (String item : words) {
System.out.print(item + " ");
}
System.out.println("");
State ohio = new State("Ohio", "DeWine");
State california = new State("California", "Newsom");
State newYork = new State("New York", "Hochul");
State massachusetts = new State("Massachusetts", "Healey");
State indiana = new State("Indiana", "Holcomb");
State hawaii = new State("Hawaii", "Honolulu");
State[] states = {ohio, california, newYork, massachusetts, indiana, hawaii};
System.out.println("states:");
myObj.toString(states);
System.out.println("");
myObj.sort2(states, 0, states.length - 1);
System.out.println("Sorted states:");
myObj.toString(states);
System.out.println("");
}
}
MergeSort.main(null);