Merging sorted arrays

Question

I'd like to know if it's ok to write like this or there is a better, prettier way to do this. The merging itself is ok. I'm more interested in dealing with the situation when one of the arrays is finished and I need to copy the rest of the other array to the result array. I wrote it in a try catch block.

int[] result = new int[fst.length + snd.length];
int fstIndex = 0;
int fstIndexValue = 0;
int sndIndex = 0;
int sndIndexValue = 0;
while (fstIndex + sndIndex != result.length) {
 try{
 fstIndexValue = fst[fstIndex];
 }catch( java.lang.ArrayIndexOutOfBoundsException e) {
 System.arraycopy(snd, sndIndex, result, fstIndex + sndIndex, snd.length - sndIndex);
 break;
 }
 try{
 sndIndexValue = snd[sndIndex];
 }catch( java.lang.ArrayIndexOutOfBoundsException e) {
 System.arraycopy(fst, fstIndex, result, fstIndex + sndIndex, fst.length - fstIndex);
 break;
 }
 if (fstIndexValue < sndIndexValue) {
 result[fstIndex + sndIndex] = fst[fstIndex++];
 } else {
 result[fstIndex + sndIndex] = snd[sndIndex++];
 }
}
return result;

• Martin Schröder: There is no limit on the length of identifiers. So why do you use e.g. fstIndex and sndIndex instead of firstIndex and secondIndex?
• Alec Teal: Runtime exceptions (like your out of bounds) can always be avoided. Actual exceptions like "cannot write to file" cannot always be avoided. Rather than catching them, ensure they cannot happen in the first place.

Answer 1

int fstIndexValue = 0;
int sndIndexValue = 0;

This is a premature optimization. You keep these values and need to update them whenever you advance an index. There may be a performance advantage or not, as the JITc is pretty smart and you're doing its job.

.... I was wrong, it just looked as an optimization, but you load both values on each iteration. Then it's just wrongly scoped variables. Declare them in the loop instead.

while (fstIndex + sndIndex != result.length) {

Actually, your loop never terminates on this condition, unless both arrays are empty. There will always be an array exhausted first so you'll terminate using a break.

---

I'd go for something like

while (true) {
 if (fstIndex==fst.length){
 System.arraycopy(snd, sndIndex, result, fstIndex + sndIndex, snd.length - sndIndex);
 break;
 }
 if (sndIndex==snd.length){
 System.arraycopy(fst, fstIndex, result, fstIndex + sndIndex, fst.length - fstIndex);
 break;
 }
 int fstIndexValue = fst[fstIndex];
 int sndIndexValue = snd[sndIndex];
 if (fstIndexValue < sndIndexValue) {
 result[fstIndex + sndIndex] = fst[fstIndex++];
 } else {
 result[fstIndex + sndIndex] = snd[sndIndex++];
 }
}

---

I really don't like the names fst and snd. Note also that fstIndexValue is no better than fstValue (compare to fstArrayValue).

The abbreviations are clear, but they don't really convey any meaning and visually they don't make it any clearer. I'd go simply for index1, index2, array1, array2, value1, and value2, which is shorter and allows to detect an error like

value1 = array1[index2];

very immediately.

Answer 2

Generally, you should do what you can not to throw an exception - it is slow and it looks bad.

In this case, you should go with:

 if (fstIndex<fst.length){
 fstIndexValue = fst[fstIndex];
 } else {
 System.arraycopy(snd, sndIndex, result, fstIndex + sndIndex, snd.length - sndIndex);
 break;
 }

Exceptions, as the name implies, suggest an exceptional condition in which the application is. In your case, it's just the algorithm's termination point - a point which you want to reach. It's not exceptional, it's desired.

Also, I don't think there ever is a good excuse to explicitly catch a java.lang.ArrayIndexOutOfBoundsException - if your code is throwing it, then you're doing something else wrong (namely, missing appropriate checks).