CODEWITHSUNDEEP
javaalgorithmmergesort
WisaF
WisaF

Reputation: 314

merged merge sort in Java

I had to write a merge sort function in Java. No problem. Well, a little, but I got through it. Then the follow up question I didn't get.

Question: Given an array A[][] such that A[i][0] is a float and A[i][1] is a nonnegative int giving the multiplicity of the value A[i][0] (here think of a big vector that's been collapsed down by combining repeated entries and recording how many got combined), write a version of merge sort that returns B[][] where B[i][0] < B[i+1][0] for all i.

Any ideas? The best I could do was merge sort and then group the equal ones, but apparently you can do it all in one step.

Upvotes: 2

Views: 726

Answers (1)

Kru
Kru

Reputation: 4235

Strage question... and using different types in these arrays is just ugly (personal point of view).

However, the most useful thing to do, is to rewrite your merge function with a Comparator. This way you can sort using whatever property you want. You would end up with a signature like void merge(A[] arr, Comparator<? super A> comp). By the way, the Java implementation of sort is a lot like this.

To solve your question you would call:

A[][] a = ...;
merge(a, new Comparator<A[]>() {
  int compare(A[] a, A[] b) {
    return ((Float)a[0]) - ((Float)b[0]);
  }
});

Upvotes: 2

Related Questions