I am making a program which implements the mergesort algorithm but instead of dividing each time in 2 parts it divides them in 3 parts each time and mergesorting them recursively. In case I confused you it is basically a mergesort but instead of mergesorting with 2 parts, you mergesort with 3 each time, sounds pretty fun huh? Well it definitely isn't.
Here is my implementation of mergesort:
public static void mergesort(int[] data) {
int elements = data.length;
int sizeLeft;
int sizeCenter;
int sizeRight;
if (elements > 2) {
if (elements % 3 == 0) {
sizeLeft = elements / 3;
sizeCenter = elements / 3;
sizeRight = elements / 3;
} else if (elements % 3 == 1) {
sizeLeft = (elements / 3) + 1;
sizeCenter = elements / 3;
sizeRight = elements / 3;
} else { //if (elements % 3 == 2)
sizeLeft = (elements / 3) + 1;
sizeCenter = elements / 3;
sizeRight = (elements / 3) + 1;
}
int[] left = makeArray(data, 0, sizeLeft);
int[] center = makeArray(data, sizeLeft, sizeCenter);
int[] right = makeArray(data, sizeLeft + sizeCenter, sizeRight);
mergesort(left);
mergesort(center);
mergesort(right);
merge(data, left, center, right);
}
}
Here is the the merge method:
public static void merge(int[] data, int[] left, int[] center, int[] right) {
int[] temp = new int[left.length + center.length + right.length];
int copiedTotal = 0;
int copiedLeft = 0;
int copiedCenter = 0;
int copiedRight = 0;
while ((copiedLeft < left.length)
&& (copiedCenter < center.length)
&& (copiedRight < right.length)) {
if ((left[copiedLeft] < center[copiedCenter])
&& (left[copiedLeft] < right[copiedRight])) {
temp[copiedTotal++] = left[(copiedLeft++)];
} else if ((center[copiedCenter] < left[copiedLeft])
&& (center[copiedCenter] < right[copiedRight])) {
temp[copiedTotal++] = center[copiedCenter++];
} else {
temp[copiedTotal++] = right[copiedRight++];
}
}
while ((copiedLeft < left.length) && (copiedCenter < center.length)) {
if (left[copiedLeft] < center[copiedCenter]) {
temp[copiedTotal++] = left[copiedLeft++];
} else{
temp[copiedTotal++] = center[copiedCenter++];
}
}
while ((copiedLeft < left.length) && (copiedRight < right.length)) {
if (left[copiedLeft] < right[copiedRight]) {
temp[copiedTotal++] = left[copiedLeft++];
} else{
temp[copiedTotal++] = right[copiedRight++];
}
}
while ((copiedCenter < center.length) && (copiedRight < right.length)) {
if (center[copiedCenter] < right[copiedRight]) {
temp[copiedTotal++] = center[copiedCenter++];
} else{
temp[copiedTotal++] = right[copiedRight++];
}
}
while (copiedLeft < left.length) {
temp[copiedTotal++] = left[copiedLeft++];
}
while (copiedCenter < center.length) {
temp[copiedTotal++] = center[copiedCenter++];
}
while (copiedRight < right.length) {
temp[copiedTotal++] = right[copiedRight++];
}
System.arraycopy(temp, 0, data, 0, left.length + center.length + right.length);
// for (int i = 0; i < data.length; i++) {
// if ((copiedRight >= right.length) && (copiedCenter >= center.length)) {
// data[i] = left[copiedLeft]; // take from left
// copiedLeft++;
// } else if ((copiedRight >= right.length) && (copiedLeft >= left.length)) {
// data[i] = center[copiedCenter]; // take from left
// copiedCenter++;
// } else if ((copiedCenter >= center.length) && (copiedLeft >= left.length)) {
// data[i] = right[copiedRight]; // take from left
// copiedRight++;
// } else if ((copiedLeft < left.length
// && left[copiedLeft] <= right[copiedRight])
// && left[copiedLeft] <= center[copiedCenter]) {
//
// data[i] = left[copiedLeft]; // take from left
// copiedLeft++;
//
// } else if ((copiedRight >= right.length) && (copiedLeft >= left.length)
// || (copiedCenter < center.length
// && center[copiedCenter] <= right[copiedRight])
// && center[copiedCenter] <= left[copiedLeft]) {
//
// data[i] = center[copiedCenter]; // take from center
// copiedCenter++;
// } else {
// data[i] = right[copiedRight];
// copiedRight++;// take from center
// }
//
// }
}
}
In the comments inside the merge method there is another merge method I tried to make but it didn't end well at all and things became way more complicated but I left it there for reference.
The problem is this doesn't work at all, for example if I have:
Input: 6 5 4 3 2 1
Then I'll have:
Output: [2, 1, 4, 3, 6, 5]
I have honestly tried so hard for this and for 2 days straight, I found only two people even hearing about this kind of mergesort and after hours searching in Google I only found a similar question here (which was too complicated to understand) and another thread in wiki answers which was never answered.
Any help would be greatly appreciated, of course I am not asking for a direct solution because I am trying to learn but tips and hints as well as what I have done wrong would greatly help me.
Thanks in advance.
It seems that the problem is that when you have an 2 element array you dont do anything with it. You should sort it. If you take your example: [6,5,4,3,2,1], in the second step of recursion you have [2,1]; [4,3] and [6,5] and you merge them like that. If you would sort them first, you would obtained the right order. In order to sort them in merge function you should add:
if ((elements==2)&&(data[1]<data[0])){
int aux = data[1];
data[1] = data[0];
data[0] = aux;
}
Hope it helps.
UPDATE
If you want to have a pure merge sort you can try (as I explained in the comment) to add the following piece of code:
if (elements==2){
int[] center = [];
int[] left = makeArray(data,0,1);
int[] right =makeArray(data,1,1);
mergesort(left); //you can call these methods or not, on a empty or 1 element array they dont have an effect
mergesort(center);
mergesort(right);
merge(data, left, center, right); //it should work well when center is an empty array
}
UPDATE 2 You can refactor the code I shown so it looks beautiful. The basic idea is that you can have an empty array in Java and your merge function deals with it properly. Hope I made my point a bit clearer.