Three Things on Format Include a header at the top of you source code that inclu

Question

Three Things on Format
Include a header at the top of you source code that includes the lab #, your name, date, problem description etc.
When naming the file use you username and the lab number For example: jsmithLab1.java
Your code is going to be read make sure to format it correctly (i.e. indent all blocks)

Lecture 2: Chapter 8 Programming Exercise 18   No PLTL  

See book as formating of algorithum is not shown well

18. Merge Sort

Write a recursive method mergeSort(int[] a, int start, int finish) that sorts an array of

integers a from index start through index finish. Test your method with an array test

of 100 random numbers.

The algorithm works as follows:

Sort the first half of the array recursively.

Sort the last half recursively.

Merge the two sorted halves together.

Merging is accomplished via a method

int[] merge(a, start, finish),

   which returns an array with the two sorted halves of a merged into a single sorted array.

This new array must be copied back to a.

Hint : To merge the two halves:

Create a new temporary array b  

leftpointer = start; // leftpointer traverses the left half of the array.
  halfway  = (start + finish)/2 ;
  rightpointer  = halfway, // rightpointer traverses the right half, and
  bpointer =  0; // bpointer traverses the new array b[].

  while ( ( leftpointer <= halfway ) AND (rightpointer <= finish) ) {
     if ( a[leftpointer]  <  a[rightpointer] ) {
         b[bpointer] = a[leftpointer] ;
         leftpointer++;
   } else {
        b[bpointer] = a[rightpointer];
        rightpointer++;
   }
     bpointer++;
  }

  if (leftpointer > halfway) {
      // copy the remainder of the right half of a  to b
  }
  if (rightpointer > finish) {
      // copy the remainder of the left half of a  to b
  }

  return b or copy back to a

Explanation / Answer

public class Mergesort { private int[] numbers; private int[] helper; private int number; public void sort(int[] values) { this.numbers = values; number = values.length; this.helper = new int[number]; mergesort(0, number - 1); } private void mergesort(int low, int high) { if (low

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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