Merge-sort in Java

Every programmer must initially think through the scheme/plan/architecture of future work, otherwise it all ends up in a mess, with complete anarchy. As with any post, you initially need a plan, let’s get started.

• 1) Let's take the topic of Merge sort for beginners.
• 2) We will create an architecture and a plan for further work.
• 3) We will work through and describe all parts of the plan.
• 4) Let's check the performance and quality.

• 2.1) What is Merge sorting.
• 2.2) Description of possible signatures.
• 2.3) Give an example.
• 2.4) Describe the implementation in Java using an example.
• 2.5) Anything extra.

Merge - merge sort in Java

Implies the principle of “divide and conquer”. What is the idea and its meaning?

1. Sorting.

   We divide the array into parts until it is equal to 1 element. Every 1 element is sorted.

2. Merger.

   Merging sorted elements.
   Based on the principle of two decks of cards. We place 2 decks of cards on the table with their values ​​up, and the card that is lowest is placed in the third resulting pile of cards. Ultimately, if we run out of cards in a certain deck, we move them one by one to the resulting deck. The result will be a merged of two sorted arrays, one new, sorted array.

The time spent is O(n log2 n). Sorting is considered quite fast. Briefly about algorithmic complexity, if anyone needs it. You can often see functions like:

Sort(A, p, q);
Merge(A, p, q, r);

This is about the same thing, only linked to indexes. The variables in them are:

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

If these variables are not described, then the one who asks to make such a function himself does not know what he wants. And you’ll have to scour Google to find out what it is, you’ll probably find it, maybe. Let's give an example of our sorting. There is an array {6, 1, 3, 5, 2, 4, 7, 8}, if its length is greater than 1, then we divide it into 2 parts and get the left part {6, 1, 3, 5}and the right part {2, 4, 7, 8}. We continue the action of dividing into 2 parts until its length is greater than 1. As a result, we get a bunch of arrays with a length of 1 element, namely: {6} {1} {3} {5} {2} {4} {7} {8}. The implementation in Java is something like this:

public int [] sortArray(int[] arrayA){ // sorting Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

Next you need to merge these arrays into 1. How is this done? To avoid going through each array multiple times, let's enter position indices for each array. Then we will go through a loop once, equal to the length of the sum of these two arrays. Take the first array and the second array, and take the first element, compare element number 1 in the first array and element number 1 in the second array ? The smaller one is placed in the resulting array. It is important here that if we took an element from the first array, then when the loop passes, it should refer to the 2nd element of the first array and to the 1st element of the second array. To do this, you need to increase the index of the second array by +1 and, when checking, subtract it from the cycle number, similarly for the first array. Is it clear why to do this? Or is nothing clear at all? :-) For example, there are 2 arrays: {1}{4}{8}and {3}{6}{7} And there is a loop:

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

On the first pass of the loop, it will turn out that arrayC[1] = {1}: we took this element from the first array. Then, when going through the second loop, we must already compare the element {4}and {3}, but in order to do this we need to take into account the position indices and the offset of both arrays, for this we enter them.

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

But that’s not all, you need to take into account that some array may end earlier. For example, there are 3 arrays: {1}{3}{5}and {6}{7}{9} The first array will end before the second one arrives, for this you need to enter a check and, in principle, the merge function is ready.

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

The hardest thing about this sorting is the principle of recursion transition. Those. we throw the left side into recursion until it is divisible by 2, and then unwind it back, in words it is very complicated and confusing, but when you try to imagine, if it’s not clear yet, then it’s a complete mess. Let's take the array: {2}{1}{4}{3}. The first sorting recursion will divide it into 2 parts and run the function again with elements 2-1 , then again with elements 2 and 1 , return them in turn, so they will get into the merge function first, and 1-2 will come out , then the recursion will return back and throw 4-3 into the merge , then 4 and 3 , after which the merge will return 3-4 , and only then the recursion will spin back again and 1-2 and 3-4 will be included in the merge , and the sorted array will be returned 1-2-3-4 . Well, that’s all, sorting consists of two functions.

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

If you write down some kind of main, you will get something like:

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

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

For me, this sorting was a complete failure, there were a million questions, but no answers, I dug through the entire Internet, re-read, watched a bunch of videos, but as always, I only found the answers myself. And only when I started writing a solution completely different from the one that flashes everywhere) But in the end it turned out similar to all the others))) Sorting is actually the simplest, the main thing is to present it interactively in action, and everything falls into place if you get the hang of it, I'll make a video)))) So far, that's all I've had enough for: Merge sort Merge-sort The most important thing is to always make a plan from the beginning. It's better to wait a little and think before you start doing anything. It may take more time, but an understanding and a solution will emerge rather than having to rewrite it a couple of times and come up with crutches. Thank you all for your time, good luck and good mood. ) PS: Criticism, good and bad, as well as questions are very welcome. )))