Write a Java program to implement merge sort. Specifically, implement one of the

Question

Write a Java program to implement merge sort. Specifically, implement one of the following functions using recurrence,

int[] merge_sort(int[] arr) Implement the function by yourself and do not use any system-provided sorting function. The function takes either an integer array or ArrayList and returns the sorted array/ArrayList. Hint: https://en.wikipedia.org/wiki/Merge_sort What to program: The skeleton of the program is given to you in MergeSort.java. Finish the program by yourself. What to submit: Submit just one copy of MergeSort.java. that contains finished program of both problem 1 and 2.

Write a Java program to implement one of the following two functions, boolean Find_Number(int[] arr, int num) The two functions take either an integer array or an integer ArrayList and an integer num as input. The function should return true if num appeasers in arr for at least once. Return false if otherwise. Implement the function by yourself and do not use any system-provided array-element searching function, such as ArrayList.contains. Requirements:

1) Use the merge sort function you implemented in the previous problem to sort the input array or ArrayList first.

2) Then try to find if num appeasers in arr.

3) No point will be given if you go through all the integers in arr one by one to find num. Instead, take advantage of the fact that arr is sorted.

Hint: You should be able to decide if num appeasers in arr by checking at most log n positions in arr where n is the length of arr. What to program: The skeleton of the program is also included in MergeSort.java. Finish the program by yourself. What to submit: Submit just one copy of MergeSort.java that contains finished program of both problem 1 and 2.

Explanation / Answer

These two below functons are written for merge sort and find_number ..

1. Find Number function will pass the array to merge sort function.

2. Mergr sort funtcion will sort the list and return the result to find_function.

See the below code..

   public static int[] mergeSort(int [] list) {
if (list.length <= 1) {
return list;
}
  
// Split the array in half
int[] first = new int[list.length / 2];
int[] second = new int[list.length - first.length];
System.arraycopy(list, 0, first, 0, first.length);
System.arraycopy(list, first.length, second, 0, second.length);
  
// Sort each half
mergeSort(first);
mergeSort(second);
  
// Merge the halves together, overwriting the original array
merge(first, second, list);
return list;
}
  
private static void merge(int[] first, int[] second, int [] result) {
// Merge both halves into the result array
// Next element to consider in the first array
int iFirst = 0;
// Next element to consider in the second array
int iSecond = 0;
  
// Next open position in the result
int j = 0;
// As long as neither iFirst nor iSecond is past the end, move the
// smaller element into the result.
while (iFirst < first.length && iSecond < second.length) {
if (first[iFirst] < second[iSecond]) {
result[j] = first[iFirst];
iFirst++;
} else {
result[j] = second[iSecond];
iSecond++;
}
j++;
}
// copy what's left
System.arraycopy(first, iFirst, result, j, first.length - iFirst);
System.arraycopy(second, iSecond, result, j, second.length - iSecond);
}
  
   static boolean Find_Number(int[] arr, int num)
   {
       array = mergeSort(int[] arr);
       for(int i =0; i <array.length;i++)
           if(array[i] == num)
               return true;
           else
               return false;
          
   }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.