# Zwei sortierte Arrays zusammenführen



## Gayson (9. Jul 2009)

Hallo!

Ich habe zwei Arrays mit vielen Elementen, und ich suche den effizientesten Weg, diese zusammenzuführen und die Sortierung zu erhalten (beide Arrays sind disjunkt). Meine erste Lösung war:


```
int[] a1 = {1,2,3,10,20};
int[] a2 = {5,7,15,25};

// Copy a1 into newA
int[] newA = Arrays.copyOf(a1, a1.length + a2.length);

// Copy a2 into newA
for(int i=0; i < a2.length; i++){
  newA[a1.length+i] = a2[i];
}

System.out.println(Arrays.toString(newA)); //=> [1, 2, 3, 10, 20, 5, 7, 15, 25]
Arrays.sort(newA);
System.out.println(Arrays.toString(newA)); //=> [1, 2, 3, 5, 7, 10, 15, 20, 25]
```

Fällt euch eine performantere Lösung ein, die ausnutzt, das beide Arrays bereits sortiert vorliegen?


----------



## Leroy42 (9. Jul 2009)

Gayson hat gesagt.:


> Fällt euch eine performantere Lösung ein, die ausnutzt, das beide Arrays bereits sortiert vorliegen?



Durchlaufe die beiden Arrays einfach und füge das aktuell kleinste Element
in das neue Array ein.


----------



## Beni (9. Jul 2009)

Nur eine Idee:

```
int[] a1;
int[] a2;

int i1 = 0;
int i2 = 0;

int i = 0;

while( ... ){
  if( a1[i1] < a2[i2] ){
    result[ i ] = a1[ i1++ ];
  }
  else{
    result[ i ] = a2[ i2++ ];
  }
}
```


----------



## Leroy42 (9. Jul 2009)

Beni hat gesagt.:


> ```
> while( ... ){...}
> ```


while (...)
Ist ja genial!


----------



## Beni (9. Jul 2009)

Hey, ich bin hier auf der Arbeit und werde nicht dafuer bezahlt im Forum rumzulungern, deshalb gibt es von mir nur Schnellschreibantworten ;-)


----------



## SchonWiederFred (9. Jul 2009)

Ein klassischer Merge 

```
import java.util.Arrays;

public class Merge
{
	/**
	 * returns { a[0], a[1], ... a[a.length-1], b[b.length-1], ... b[1], b[0] }
	 */
	private static int[] mirror(int[] a, int[] b)
	{
		int i = a.length + b.length;
		a = Arrays.copyOf(a, i);
		for (int x : b)
			a[--i] = x;
		return a;
	}

	/**
	 * returns a sorted array containing the elements
	 * of the already sorted arrays a and b
	 */
	public static int[] merge(int[] a, int[] b)
	{
		a = mirror(a, b);
		b = new int[a.length];
		int left = 0, right = b.length - 1;
		int i = 0;
		while (left <= right)
			if (a[left] < a[right])
				b[i++] = a[left++];
			else
				b[i++] = a[right--];
		assert i == b.length;
		return b;
	}

	public static void main(String[] args)
	{
		int[] a1 = { 1, 2, 3, 10, 20 };
		int[] a2 = { 5, 7, 15, 25 };

		System.out.println(Arrays.toString(merge(a1, a2)));
	}
}
```


----------



## SchonWiederFred (9. Jul 2009)

Eine Alternativlösung mit weniger Kopiererei aber deutlich komplizierterem Kontrollfluss 

```
import java.util.Arrays;

public class Merge
{
	/**
	 * returns a sorted array containing the elements
	 * of the already sorted arrays a and b
	 */
	public static int[] merge(int[] a, int[] b)
	{
		if (a.length == 0) return b;
		if (b.length == 0) return a;
		int[] c = new int[a.length + b.length];
		int x = 0, y = 0, z = 0;
		while (true)
		{
			if (a[x] < b[y])
			{
				c[z++] = a[x++];
				if (x == a.length)
				{
					System.arraycopy(b, y, c, z, c.length - z);
					return c;
				}
			}
			else
			{
				c[z++] = b[y++];
				if (y == b.length)
				{
					System.arraycopy(a, x, c, z, c.length - z);
					return c;
				}
			}
		}
	}

	public static void main(String[] args)
	{
		int[] a1 = { 1, 2, 3, 10, 20 };
		int[] a2 = { 5, 7, 15, 25 };

		System.out.println(Arrays.toString(merge(a1, a2)));
	}
}
```


----------



## Leroy42 (9. Jul 2009)

SchonWiederFred hat gesagt.:


> Eine Alternativlösung mit weniger Kopiererei



Hääh? :shock:

Es müssen doch immer gleichviel Elemente kopiert werden: Die Elemente
beider Arrays!


----------



## SchonWiederFred (9. Jul 2009)

Meine erste Lösung erstellt zwei neue Arrays, die zweite Lösung dagegen nur eins.


----------



## Leroy42 (9. Jul 2009)

Und wo wird weniger bei deiner zweiten Lösung kopiert?

Oder: *welche Elemente werden nicht kopiert*?


----------



## SchonWiederFred (9. Jul 2009)

Bei der ersten Lösung wird in mirror() noch ein Zwischenarray erstellt. Es wird also jedes Element doppelt kopiert, einmal in das Zwischenarray und einmal in das Zielarray. Dieses Zwischenarray benötigt die zweite Lösung nicht. Klar?

In C++ muss man den Kram übrigens wie so oft nicht selbst programmieren.

```
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    std::vector<int> a = {1,2,3,10,20};
    std::vector<int> b = {5,7,15,25};

    std::vector<int> c(a.size() + b.size());
    std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());

    std::copy(c.begin(), c.end(), std::ostream_iterator<int>(std::cout, "\n"));
}
```


----------



## Leroy42 (9. Jul 2009)

SchonWiederFred hat gesagt.:


> Bei der ersten Lösung wird in mirror() noch ein Zwischenarray erstellt. Es wird also jedes Element doppelt kopiert, einmal in das Zwischenarray und einmal in das Zielarray. Dieses Zwischenarray benötigt die zweite Lösung nicht.



Und wozu war dieses Zwischenarray überhaupt nötig?


----------



## SchonWiederFred (9. Jul 2009)

Um den Kontrollfluss zu vereinfachen. Schau Dir den Code doch einfach mal an 
a wird unverändert übernommen, und b wird gespiegelt. Sie stoßen mit ihren großen Enden aneinander.
Daher braucht man keine Sonderbehandlung, wenn ein Array fertig kopiert ist.
Es wird einfach so lange weitergemacht, bis die Indizes aneinander vorbeigelaufen sind.


----------



## SlaterB (9. Jul 2009)

ein paar Längenprüfungen müssen aber auch nicht so kompliziert sein, statt des  System.arraycopy ginge wohl auch

```
.
        while (x < a.length || y < b.length)
        {
            if (x < a.length && (y >= b.length || a[x] < b[y]))
            {
                c[z++] = a[x++];
            }
            else
            {
                c[z++] = b[y++];
            }
        }
```
(nur grob geprüft)

edit: noch korrigiert, 4 Längenprüfungen statt 3 sind schon wieder etwas unschön


----------

