3

Let's say you have three String arrays for example:

array1: as,hi,ji

array2: fo,gl

array3: gt,my,wx,zq

As you can see, the individual arrays are sorted. How would you merge them, with the merged array also being sorted? I know you can first write a method to merge a pair of them, then merge the final one with this new one. Mostly I am just confused if you should first merge then sort or vice versa. Would merge sort be useful?

Improve this question
5
  • 4
    Mergesort is more than useful. It is easy to implement, comprehensible, and very effective. See en.wikipedia.org/wiki/… Commented Feb 27, 2014 at 23:07
  • 3
    If they are already sorted, you can just use a "Merge" to create the final array, i.e. tak the lowest item left in the 3 three arrays and move it to the output array Commented Feb 27, 2014 at 23:12
  • possible duplicate of Merge Sort Java Commented Feb 27, 2014 at 23:28
  • @Jean-RémyRevy: I don't see how this is a duplicate (anymore). The link describes merge sort, but not how to explicitly merge two arrays together. You can definitely do one without the other. Commented May 10, 2014 at 21:03
  • Please stop editing your question, it will not help you. Commented May 10, 2014 at 22:47

2 Answers 2

Reset to default
3

I would use something like

public static String[] join(String[]... sas) {
    String[] result = new String[0];
    for (String[] sa : sas) {
        result = Arrays.copyOf(result, result.length + sa.length);
        System.arraycopy(sa, 0, result, result.length - sa.length, sa.length);
    }
    return result;
}

and then

String[] s = join(s1, s2, s3);
Arrays.sort(s);

Maybe there is any external library handling this.

Related the efectivity, sorting the array has complexity ~ N * log N (merge-sort) which is worse than copying (~ N), so the better way is to unite the array and sort once than sort each particular merge. Java class Arrays uses the merge-sort internally.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Here is a general idea, despite the 3 String arrays are sorted already, I added Arrays.sort() in case the arrays you are using are not sorted

String[] a1 = {"as", "hi", "ji"};
String[] a2 = {"fo", "gl"};
String[] a3 = {"gt", "my", "wx", "zq"};

List<String> list1 = new ArrayList<String>(Arrays.asList(a1));
list1.addAll(Arrays.asList(a2));
list1.addAll(Arrays.asList(a3));
String[] all = list1.toArray(new String[list1.size()]);
Arrays.sort(all);

for(String a : all) {
   System.out.println(a);
}
Improve this answer

Comments