void merge(int arr[], int l, int m, int r)
{
// Find the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays */
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];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
// MISSING CODE #1
arr[k] = L[i];
i++;
}
else {
// MISSING CODE #2
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
int[] integers = new int[10];
integers[0] = 9;
integers[1] = 3;
integers[2] = 2;
integers[3] = 5;
integers[4] = 4;
integers[5] = 8;
integers[6] = 6;
integers[7] = 7;
integers[8] = 1;
integers[9] = 0;
sort(integers, 0, integers.length - 1);
for (int i = 0; i < integers.length; i++) {
System.out.println(integers[i]);
}
void merge(String arr[], int l, int m, int r)
{
// Find the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
String[] L = new String[n1];
String[] R = new String[n2];
/* Copy data to temp arrays */
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];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i].compareTo(R[j]) <= 0) {
// MISSING CODE #1
arr[k] = L[i];
i++;
}
else {
// MISSING CODE #2
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(String arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
String[] strings = new String[10];
strings[0] = "Arkansas";
strings[1] = "California";
strings[2] = "Alabama";
strings[3] = "Nebraska";
strings[4] = "South Dakota";
strings[5] = "Alaska";
strings[6] = "Montana";
strings[7] = "Florida";
strings[8] = "South Carolina";
strings[9] = "Georgia";
sort(strings, 0, strings.length - 1);
for (int i = 0; i < strings.length; i++) {
System.out.println(strings[i]);
}
class Country {
private String name;
public Country(String name) {
this.name = name;
}
public String getName() {
return this.name;
}
}
void merge(Country arr[], int l, int m, int r)
{
// Find the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
Country[] L = new Country[n1];
Country[] R = new Country[n2];
/* Copy data to temp arrays */
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];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i].getName().compareTo(R[j].getName()) <= 0) {
// MISSING CODE #1
arr[k] = L[i];
i++;
}
else {
// MISSING CODE #2
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(Country arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
Country[] strings = new Country[10];
strings[0] = new Country("Argentina");
strings[1] = new Country("Ecuador");
strings[2] = new Country("New Zealand");
strings[3] = new Country("China");
strings[4] = new Country("South Korea");
strings[5] = new Country("Brazil");
strings[6] = new Country("Paraguay");
strings[7] = new Country("Japan");
strings[8] = new Country("Switzerland");
strings[9] = new Country("Germany");
sort(strings, 0, strings.length - 1);
for (int i = 0; i < strings.length; i++) {
System.out.println(strings[i].getName());
}
int binarySearch(int arr[], int left, int right, int search) {
// if right is less than left, then it is not in the array
if (right >= left) {
int mid = (left + right) / 2;
if (arr[mid] == search) {
// if the middle is the value you are searching for, return the index of the middle
return mid;
} else if (arr[mid] > search) {
// if search is less than the middle, search the lower half
return binarySearch(arr, left, mid, search);
} else {
// if search is greater than the middle, search the upper half
return binarySearch(arr, mid, right, search);
}
}
return -1;
}
int array[] = {1, 3, 5, 7, 9, 23, 45, 67};
System.out.println(binarySearch(array, 0, array.length, 45));
int binarySearch(int arr[], int left, int right, int search) {
// if right is less than left, then it is not in the array
if (right >= left) {
int mid = (left + right) / 2;
if (arr[mid] == search) {
// if the middle is the value you are searching for, return the index of the middle
return mid;
} else if (arr[mid] > search) {
// if search is less than the middle, search the lower half
return binarySearch(arr, left, mid, search);
} else {
// if search is greater than the middle, search the upper half
return binarySearch(arr, mid, right, search);
}
}
return -1;
}
void merge(int arr[], int l, int m, int r)
{
// Find the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays */
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];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
// MISSING CODE #1
arr[k] = L[i];
i++;
}
else {
// MISSING CODE #2
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
int[] array = {5, 6, 3, 1, 8, 9, 4, 7, 2};
sort(array, 0, array.length - 1);
System.out.println(binarySearch(array, 0, array.length, 7));