Merge sort.. help me plz - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Merge sort.. help me plz

doubleukdoubleuk Posts: 1Member
[color=Blue]I have to change this 2-way partitioning merge sort to the 4-way partitioning merge sort.. how can I change??[/color]

public class Merge {

public static void sort(int[] a) {
if (a.length >= 2) {
int halfLength = a.length / 2;
int[] firstHalf = new int[halfLength];
int[] lastHalf = new int[a.length - halfLength];

divide(a, firstHalf, lastHalf);
sort(firstHalf);
sort(lastHalf);
merge(a, firstHalf, lastHalf);
}
}

private static void divide(int[] a, int[] firstHalf, int[] lastHalf) {
for (int i = 0; i < firstHalf.length; i++)
firstHalf[i] = a[i];
for (int i = 0; i < lastHalf.length; i++)
lastHalf[i] = a[firstHalf.length + i];
}

private static void merge(int[] a, int[] firstHalf, int[] lastHalf) {
int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
while ((firstHalfIndex < firstHalf.length)
&& (lastHalfIndex < lastHalf.length)) {
if (firstHalf[firstHalfIndex] < lastHalf[lastHalfIndex]) {
a[aIndex] = firstHalf[firstHalfIndex];

firstHalfIndex++;
} else {
a[aIndex] = lastHalf[lastHalfIndex];

lastHalfIndex++;
}
aIndex++;
}
while (firstHalfIndex < firstHalf.length) {
a[aIndex] = firstHalf[firstHalfIndex];
aIndex++;
firstHalfIndex++;
}
while (lastHalfIndex < lastHalf.length) {
a[aIndex] = lastHalf[lastHalfIndex];
aIndex++;
lastHalfIndex++;
}
}
public static void main(String[] args){
int[] arr = { 3,9,2,1,10,11,6,4,15 };

Merge.sort(arr);

for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + " ");
}

}
}
Sign In or Register to comment.