[alvin75]

Here is the merge sort algorithm to sort an array of strings in lexicographic order:

/**
   This class sorts an array, using the merge sort algorithm.
*/
public class MergeSorter
{
   private int[] a;

   /**
      Constructs a merge sorter.
      @param anArray the array to sort
   */
   public MergeSorter(int[] anArray)
   {
      a = anArray;
   }
   
   /**
      Sorts the array managed by this merge sorter.
   */
   public void sort()
   {  
      if (a.length <= 1) return;
      int[] first = new int[a.length / 2];
      int[] second = new int[a.length - first.length];
      // Copy the first half of a into first, the second half into second
      for (int i = 0; i < first.length; i++) { first[i] = a[i]; }
      for (int i = 0; i < second.length; i++) 
      { 
         second[i] = a[first.length + i]; 
      }
      MergeSorter firstSorter = new MergeSorter(first);
      MergeSorter secondSorter = new MergeSorter(second);
      firstSorter.sort();
      secondSorter.sort();
      merge(first, second);
   }

   /**
      Merges two sorted arrays into the array managed by this merge sorter. 
      @param first the first sorted array
      @param second the second sorted array
   */
   private void merge(int[] first, int[] second)
   {  
      int iFirst = 0; // Next element to consider in the first array
      int iSecond = 0; // Next element to consider in the second array
      int j = 0; // Next open position in a

      // As long as neither iFirst nor iSecond is past the end, move
      // the smaller element into a
      while (iFirst < first.length && iSecond < second.length)
      {  
         if (first[iFirst] < second[iSecond])
         {  
            a[j] = first[iFirst];
            iFirst++;
         }
         else
         {  
            a[j] = second[iSecond];
            iSecond++;
         }
         j++;
      }

      // Note that only one of the two loops below copies entries
      // Copy any remaining entries of the first array
      while (iFirst < first.length) 
      { 
         a[j] = first[iFirst]; 
         iFirst++; j++;
      }
      // Copy any remaining entries of the second half
      while (iSecond < second.length) 
      { 
         a[j] = second[iSecond]; 
         iSecond++; j++;
      }
   }
}

Here is the tester class provided:

import java.util.Arrays;

/**
   This class tests the MergeSorter class to sort 
   an array of strings.
*/
public class MergeSorterTester
{  
   public static void main(String[] args)
   { 
      String[] a = { "Able", "was", "I", "ere", "I", "saw", "Elba" };
      MergeSorter m = new MergeSorter(a);
      m.sort();
      System.out.println(Arrays.toString(a));
      System.out.println("Expected: [Able, Elba, I, I, ere, saw, was]");
   }
}

The error I keep getting is that on the tester class on line 12:

MergeSorter m = new MergeSorter(a); 

I keep getting the error: The constructor MergeSorter(String []) is undefined
I'm sorta new to programming so I would really appreciate any help. Thanks.

[jon.kiparsky]

 public MergeSorter(int[] anArray)

Your MergeSorter expects an array of ints, not Strings. You might want to read up on the Comparable interface, which would allow you to sort any array of objects which declare an ability to compare themselves to some object of similar type using the compareTo() method.

If you're not familiar with interfaces and how you'd make use of this, then there's a whole swath of Java that you should probably read up on. Start here and play with the ideas you find there. You'll probably come up with some useful questions. Ask those.

[alvin75]

jon.kiparsky, on 25 February 2013 - 10:07 PM, said:

 public MergeSorter(int[] anArray)

Your MergeSorter expects an array of ints, not Strings. You might want to read up on the Comparable interface, which would allow you to sort any array of objects which declare an ability to compare themselves to some object of similar type using the compareTo() method.

If you're not familiar with interfaces and how you'd make use of this, then there's a whole swath of Java that you should probably read up on. Start here and play with the ideas you find there. You'll probably come up with some useful questions. Ask those.

okay i am trying to make mergeSorter work for Strings instead of ints. here is what i have so far:

/**
   This class sorts an array, using the merge sort algorithm.
*/
public class MergeSorter
{
   private String[] a;

   /**
      Constructs a merge sorter.
      @param anArray the array to sort
   */
   public MergeSorter(String[] anArray)
   {
      a = anArray;
   }
   
   /**
      Sorts the array managed by this merge sorter.
   */
   public void sort()
   {  
      if (a.length <= 1) return;
      String[] first = new String[a.length / 2];
      String[] second = new String[a.length - first.length];
      // Copy the first half of a into first, the second half into second
      for (int i = 0; i < first.length; i++) { first[i] = a[i]; }
      for (int i = 0; i < second.length; i++) 
      { 	
         second[i] = a[first.length + i]; 
      }
      MergeSorter firstSorter = new MergeSorter(first);
      MergeSorter secondSorter = new MergeSorter(second);
      firstSorter.sort();
      secondSorter.sort();
      merge(first, second);
   }

   /**
      Merges two sorted arrays into the array managed by this merge sorter. 
      @param first the first sorted array
      @param second the second sorted array
   */
   private void merge(String[] first, String[] second)
   {  
      int iFirst = 0; // Next element to consider in the first array
      int iSecond = 0; // Next element to consider in the second array
      int j = 0; // Next open position in a

      // As long as neither iFirst nor iSecond is past the end, move
      // the smaller element into a
      while (iFirst < first.length && iSecond < second.length)
      {  
         if (first[iFirst].compareTo(second[iSecond]))
         {  
            a[j] = first[iFirst];
            iFirst++;
         }
         else
         {  
            a[j] = second[iSecond];
            iSecond++;
         }
         j++;
      }

      // Note that only one of the two loops below copies entries
      // Copy any remaining entries of the first array
      while (iFirst < first.length) 
      { 
         a[j] = first[iFirst]; 
         iFirst++; j++;
      }
      // Copy any remaining entries of the second half
      while (iSecond < second.length) 
      { 
         a[j] = second[iSecond]; 
         iSecond++; j++;
      }
   }
}

but on line 53:

if (first[iFirst].compareTo(second[iSecond]))

I get the error: "Type Mismatch: cannot convert from int to boolean"
Can you tell me what I'm doing wrong? or how I can fix this program?