# MergeSort

• February 16th, 2010, 08:06 PM
mgutierrez19
MergeSort
I am trying to implement recursive mergesort algorithm and it is almost done the only thing is that if i want to mergesort ( 7, 1 ,2, 3, 5, 6, 8, 4) when i run the program my output is (0, 0, 1, 2, 3, 4, 5, 6, 7, 8)

What is wrong with my code???

Code :

```import java.util.*; import java.io.*;   public class MergeSort {   public static void mergeSort(double[] a, int length) { Sort(a, 0, a.length - 1); } public static void Sort(double[] a, int left, int right) { if (left < right) { int mid = (left + right) / 2; // sort the first and the second half Sort(a, left, mid); Sort(a, mid + 1, right); merge(a, left, mid, right); } } public static void merge(double[] a, int left, int mid, int right) {   double[] b = new double[right - left + 1]; // merge both halves into a temporary array b   int index1 = left; // next element to consider in the first range int index2 = mid + 1; int last = right; int index = 0; // next open position in b   // as long as neither i1 nor i2 past the end, move the smaller into b while(index1 <= mid && index2 <= last) { if(a[index1] < a[index2]) { b[index] = a[index1]; index1++; } else { b[index] = a[index2]; index2++; } index++; }   // note that only one of the two while loops // below is executed   // copy any remaining entries of the first half while (index1 <= mid) { b[index] = a[index1]; index1++; index++; }   // copy any remaining entries of the second half while (index2 <= last) { b[index] = a[index2]; index2++; index++; } int s = 0; // copy back from the temporary array for(int i = left; i <= right; i++) { a[i] = b[s]; s++; } }   public static void main(String[] args)throws FileNotFoundException { Scanner input = new Scanner(new FileReader("input.txt"));   int count = 0; int numOfElements = 0; double[] array = new double[10];     while(input.hasNextDouble()) { array[count] = input.nextDouble(); count++; } System.out.println("Unsorted Array"); for(int i = 0; i < count; i++) { System.out.print(array[i] + " "); } System.out.println(); mergeSort(array, array.length); System.out.println("Sorted Array"); for(int i = 0; i < count; i++) { System.out.print(array[i] + " "); }   input.close(); } }```
• February 16th, 2010, 08:13 PM
mgutierrez19
Re: MergeSort
correction my output when i run the program is (0,0,1,2,3,4,5,6) so it leaves out that last two integers of my array
• February 16th, 2010, 10:22 PM
CT&SC
Re: MergeSort
I don't see any problem with your code right off. When I run your code and manually set the array to be random-ish values, it works. Is it possible you aren't reading what you think you're reading from the file?
• March 3rd, 2010, 08:46 PM
```function mergesort(m) var list left, right, result if length(m) ≤ 1 return m else var middle = length(m) / 2 for each x in m up to middle - 1 add x to left for each x in m at and after middle add x to right left = mergesort(left) right = mergesort(right) if last(left) ≤ first(right) append right to left return left result = merge(left, right) return result   function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) if length(left) > 0 append rest(left) to result if length(right) > 0 append rest(right) to result return result```