Прежде всего, я предполагаю, что это скорее академический, чем практический, поскольку вы не используете встроенную функцию сортировки. Это, как говорится, поможет вам двигаться в правильном направлении:
Обычно можно рассматривать сортировку слияния как два разных метода: функцию merge(), которая объединяет два отсортированных списка в один отсортированный список и mergeSort(), который рекурсивно разбивает список на отдельные списки элементов. Поскольку список отдельных элементов уже отсортирован, вы затем объединяете все списки вместе в один большой отсортированный список.
Вот некоторые экспромтом псевдо-код:
merge(A, B):
C = empty list
While A and B are not empty:
If the first element of A is smaller than the first element of B:
Remove first element of A.
Add it to the end of C.
Otherwise:
Remove first element of B.
Add it to the end of C.
If A or B still contains elements, add them to the end of C.
mergeSort(A):
if length of A is 1:
return A
Split A into two lists, L and R.
Q = merge(mergeSort(L), mergeSort(R))
return Q
Может быть, поможет прояснить, где вы хотите пойти.
Если нет, в wikipedia всегда есть MergeSort.
Дополнительная:
Чтобы помочь вам, вот некоторые комментарии встроенные в вашем коде.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
// what do lHigh and rHigh represent?
int elements = (rHigh - lHigh +1) ;
int[] temp = new int[elements];
int num = left;
// what does this while loop do **conceptually**?
while ((left <= lHigh) && (right <= rHigh)){
if (a[left] <= a[right]) {
// where is 'pos' declared or defined?
temp[pos] = a[left];
// where is leftLow declared or defined? Did you mean 'left' instead?
leftLow ++;
}
else {
temp[num] = a[right];
right ++;
}
num++;
}
// what does this while loop do **conceptually**?
while (left <= right){
// At this point, what is the value of 'num'?
temp[num] = a[left];
left += 1;
num += 1;
}
while (right <= rHigh) {
temp[num] = a[right];
right += 1;
num += 1;
}
// Maybe you meant a[i] = temp[i]?
for (int i=0; i < elements; i++){
// what happens if rHigh is less than elements at this point? Could
// rHigh ever become negative? This would be a runtime error if it did
a[rHigh] = temp[rHigh];
rHigh -= 1;
}
Я целенаправленно расплывчато, поэтому вы думаете об алгоритме. Попробуйте вставить свои собственные комментарии в код. Если вы можете написать то, что концептуально происходит, вам может не понадобиться переполнение стека :)
Мои мысли здесь в том, что вы не реализуете это правильно. Это потому, что похоже, что вы только касаетесь элементов массива только один раз (или только один раз). Это означает, что у вас есть худший сценарий O(N) Сортировка обычно занимает не менее O(N * log N), и из того, что я знаю, более простые версии сортировки слияния на самом деле - O(N^2).
Подробнее:
В наиболее упрощенной реализации сортировки слиянием, я бы ожидал увидеть какую-то recursion в методе сортировки слиянием(). Это связано с тем, что сортировка слияния обычно определяется рекурсивно. Есть способы сделать это итеративно, используя петли for и while, но я определенно не рекомендую это как инструмент обучения, пока вы не получите его рекурсивно.
Честно говоря, я предлагаю взять либо мой псевдокод, либо псевдокод, который вы можете найти в статье википедии, чтобы реализовать это и начать с вашего кода. Если вы это сделаете, и он работает неправильно, отправьте его здесь, и мы поможем вам разобраться в изломах.
Cheers!
И наконец:
// Precondition: array[left..lHigh] is sorted and array[right...rHigh] is sorted.
// Postcondition: array[left..rHigh] contains the same elements of the above parts, sorted.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
// temp[] needs to be as large as the number of elements you're sorting (not half!)
//int elements = (rHigh - lHigh +1) ;
int elements = rHigh - left;
int[] temp = new int[elements];
// this is your index into the temp array
int num = left;
// now you need to create indices into your two lists
int iL = left;
int iR = right;
// Pseudo code... when you code this, make use of iR, iL, and num!
while(temp is not full) {
if(left side is all used up) {
copy rest of right side in.
make sure that at the end of this temp is full so the
while loop quits.
}
else if (right side is all used up) {
copy rest of left side in.
make sure that at the end of this temp is full so the
while loop quits.
}
else if (array[iL] < array[iR]) { ... }
else if (array[iL] >= array[iR]) { ... }
}
}
Умм .. вы пытаетесь, чтобы он работает правильно или просто скомпилировать ?! – notnoop
в merge(), первый вызов слияния должен начинаться с центра, а не от начала до конца. –
в merge(), вызов mergeSort должен быть 'mergeSort (newArray, start, center, center + 1, end);' –