also gut geschrieben? static void mergeSort(int[] array) { msort(array, 0, array.length - 1); } static void msort(int[] array, int left, int right) { if (right > left) { int mid = (right + left) / 2; msort(array, left, mid); msort(array, mid + 1, right); int[] b = new int[array.length]; for (int k = left; k <= mid; k++) b[k] = array[k]; for (int k = mid + 1; k <= right; k++) b[right + mid + 1 - k] = array[k]; int i = left; int j = right; for (int k = left; k <= right; k++) { if (b[i] < b[j]) array[k] = b[i++]; else array[k] = b[j--]; } } }
(1 votes)
Loading...
Well, what does “good” mean, that’s a normal mere place.
Mergesort is no longer a good sorting algorithm, since this O(n) additional memory requires an n large input quantity.
It should be called, even if it runs in O(n log(n) in the worst case, Quicksort is faster in the avg case and does not need an extra memory.
This is sometimes the reason why Mergesort is not actually implemented anywhere.
For this purpose, these algorithms should rather be used for libraries, as they are tested and cover any edge cases better.
Look at std::sort<>() from the c++ standard library, the algorithm implemented there is called “Introsort” and is the fastest what goes on with comparison-oriented sorting methods.
Is a mixture of Quicksort, Heapsort and Insertion Place, and if you don’t need a stable algorithm that you should use.
LG
do you understand mergesort right now, I don’t understand
So I treated him in my studies, so I understand him.
There are several versions of it, a recursive and a non-recursive.
The principle is relatively simple, a list is simply recursively divided into n large sublists, which are then put together correctly sorted step by step.
https://youtu.be/ZRPoEKHXTJg
Consider that the recursions are processed in succession.