Merge Sort Algorithm

0488

Algorithm Learning Journey

The Merge Sort algorithm is an algorithm that has the principle/way of dividing and merging. What is meant by dividing is breaking an array into small fractions that cannot be divided, then the array is sorted at the same time as the process of merging the array. In the combining stage the sorting process occurs, not in the dividing/splitting process.

Illustration
There is an array.

Then we break array into 2 parts (left & right). By creating a new array then entering the array values.

Then break again until n(array length) <= 1.

Then the next stage, the values ​​are combined and sorted, smaller values ​​on the left side & larger values ​​on the right.

For the complete process.

Code Implementation
Java 

<span>public</span> <span>static</span> <span>void</span> <span>mergeSort</span><span>(</span><span>int</span><span>[]</span> <span>array</span><span>)</span> <span>{</span>
    <span>int</span> <span>n</span> <span>=</span> <span>array</span><span>.</span><span>length</span><span>;</span>
    <span>if</span><span>(</span><span>n</span> <span><=</span> <span>1</span><span>)</span> <span>return</span><span>;</span>
    <span>int</span> <span>middle</span> <span>=</span> <span>(</span><span>n</span> <span>/</span> <span>2</span><span>);</span>
    <span>int</span><span>[]</span> <span>left</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>middle</span><span>];</span>
    <span>int</span><span>[]</span> <span>right</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>n</span> <span>-</span> <span>middle</span><span>];</span>
    <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>middle</span><span>;</span> <span>i</span><span>++)</span> <span>{</span>
        <span>left</span><span>[</span><span>i</span><span>]</span> <span>=</span> <span>array</span><span>[</span><span>i</span><span>];</span>
    <span>}</span>
    <span>int</span> <span>supportIndex</span> <span>=</span> <span>0</span><span>;</span>
    <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>middle</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>;</span> <span>i</span><span>++)</span> <span>{</span>
        <span>right</span><span>[</span><span>supportIndex</span><span>++]</span> <span>=</span> <span>array</span><span>[</span><span>i</span><span>];</span>
    <span>}</span>
    <span>mergeSort</span><span>(</span><span>left</span><span>);</span>
    <span>mergeSort</span><span>(</span><span>right</span><span>);</span>
    <span>merge</span><span>(</span><span>left</span><span>,</span> <span>right</span><span>,</span> <span>array</span><span>);</span>
<span>}</span>
<span>private</span> <span>static</span> <span>void</span> <span>merge</span><span>(</span><span>int</span><span>[]</span> <span>left</span><span>,</span> <span>int</span><span>[]</span> <span>right</span><span>,</span> <span>int</span><span>[]</span> <span>array</span><span>)</span> <span>{</span>
    <span>int</span> <span>leftIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>rightIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>arrayIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>leftSize</span> <span>=</span> <span>left</span><span>.</span><span>length</span><span>,</span>
        <span>rightSize</span> <span>=</span> <span>right</span><span>.</span><span>length</span><span>;</span>
    <span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>&&</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>if</span><span>(</span><span>left</span><span>[</span><span>leftIndex</span><span>]</span> <span><</span> <span>right</span><span>[</span><span>rightIndex</span><span>])</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
        <span>}</span>
        <span>else</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
        <span>}</span>
    <span>}</span>
    <span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
    <span>}</span>
    <span>while</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
    <span>}</span>
<span>}</span>
<span>public</span> <span>static</span> <span>void</span> <span>mergeSort</span><span>(</span><span>int</span><span>[]</span> <span>array</span><span>)</span> <span>{</span>
    <span>int</span> <span>n</span> <span>=</span> <span>array</span><span>.</span><span>length</span><span>;</span>
    <span>if</span><span>(</span><span>n</span> <span><=</span> <span>1</span><span>)</span> <span>return</span><span>;</span>

    <span>int</span> <span>middle</span> <span>=</span> <span>(</span><span>n</span> <span>/</span> <span>2</span><span>);</span>
    <span>int</span><span>[]</span> <span>left</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>middle</span><span>];</span>
    <span>int</span><span>[]</span> <span>right</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>n</span> <span>-</span> <span>middle</span><span>];</span>

    <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>middle</span><span>;</span> <span>i</span><span>++)</span> <span>{</span>
        <span>left</span><span>[</span><span>i</span><span>]</span> <span>=</span> <span>array</span><span>[</span><span>i</span><span>];</span>
    <span>}</span>
    <span>int</span> <span>supportIndex</span> <span>=</span> <span>0</span><span>;</span>
    <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>middle</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>;</span> <span>i</span><span>++)</span> <span>{</span>
        <span>right</span><span>[</span><span>supportIndex</span><span>++]</span> <span>=</span> <span>array</span><span>[</span><span>i</span><span>];</span>
    <span>}</span>

    <span>mergeSort</span><span>(</span><span>left</span><span>);</span>
    <span>mergeSort</span><span>(</span><span>right</span><span>);</span>
    <span>merge</span><span>(</span><span>left</span><span>,</span> <span>right</span><span>,</span> <span>array</span><span>);</span>
<span>}</span>

<span>private</span> <span>static</span> <span>void</span> <span>merge</span><span>(</span><span>int</span><span>[]</span> <span>left</span><span>,</span> <span>int</span><span>[]</span> <span>right</span><span>,</span> <span>int</span><span>[]</span> <span>array</span><span>)</span> <span>{</span>
    <span>int</span> <span>leftIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>rightIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>arrayIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>leftSize</span> <span>=</span> <span>left</span><span>.</span><span>length</span><span>,</span>
        <span>rightSize</span> <span>=</span> <span>right</span><span>.</span><span>length</span><span>;</span>

    <span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>&&</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>if</span><span>(</span><span>left</span><span>[</span><span>leftIndex</span><span>]</span> <span><</span> <span>right</span><span>[</span><span>rightIndex</span><span>])</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
        <span>}</span>
        <span>else</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
        <span>}</span>
    <span>}</span>

    <span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
    <span>}</span>
    <span>while</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
    <span>}</span>
<span>}</span>
public static void mergeSort(int[] array) {
    int n = array.length;
    if(n <= 1) return;

    int middle = (n / 2);
    int[] left = new int[middle];
    int[] right = new int[n - middle];

    for(int i = 0; i < middle; i++) {
        left[i] = array[i];
    }
    int supportIndex = 0;
    for(int i = middle; i < n; i++) {
        right[supportIndex++] = array[i];
    }

    mergeSort(left);
    mergeSort(right);
    merge(left, right, array);
}

private static void merge(int[] left, int[] right, int[] array) {
    int leftIndex = 0,
        rightIndex = 0,
        arrayIndex = 0,
        leftSize = left.length,
        rightSize = right.length;

    while(leftIndex < leftSize && rightIndex < rightSize) {
        if(left[leftIndex] < right[rightIndex]) {
            array[arrayIndex++] = left[leftIndex++];
        }
        else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }

    while(leftIndex < leftSize) {
        array[arrayIndex++] = left[leftIndex++];
    }
    while(rightIndex < rightSize) {
        array[arrayIndex++] = right[rightIndex++];
    }
}

Enter fullscreen mode Exit fullscreen mode

This code runs and works, but it’s not effective enough, let’s fix it. First when looking at this code, like 1 thing we want to do is move the array values ​​to the left and right arrays. 

<span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>middle</span><span>;</span> <span>i</span><span>++)</span> <span>{</span>
    <span>left</span><span>[</span><span>i</span><span>]</span> <span>=</span> <span>array</span><span>[</span><span>i</span><span>];</span>
<span>}</span>
<span>int</span> <span>supportIndex</span> <span>=</span> <span>0</span><span>;</span>
<span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>middle</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>;</span> <span>i</span><span>++)</span> 
    <span>right</span><span>[</span><span>supportIndex</span><span>++]</span> <span>=</span> <span>array</span><span>[</span><span>i</span><span>];</span>
<span>}</span>
<span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>middle</span><span>;</span> <span>i</span><span>++)</span> <span>{</span>
    <span>left</span><span>[</span><span>i</span><span>]</span> <span>=</span> <span>array</span><span>[</span><span>i</span><span>];</span>
<span>}</span>
<span>int</span> <span>supportIndex</span> <span>=</span> <span>0</span><span>;</span>
<span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>middle</span><span>;</span> <span>i</span> <span><</span> <span>n</span><span>;</span> <span>i</span><span>++)</span> 
    <span>right</span><span>[</span><span>supportIndex</span><span>++]</span> <span>=</span> <span>array</span><span>[</span><span>i</span><span>];</span>
<span>}</span>
for(int i = 0; i < middle; i++) {
    left[i] = array[i];
}
int supportIndex = 0;
for(int i = middle; i < n; i++) 
    right[supportIndex++] = array[i];
}

Enter fullscreen mode Exit fullscreen mode

So let’s fix with a function on Arrays. 

<span>import</span> <span>java.util.Arrays</span><span>;</span>
<span>...</span>
<span>// Nice</span>
<span>left</span> <span>=</span> <span>Arrays</span><span>.</span><span>copyOfRange</span><span>(</span><span>array</span><span>,</span> <span>0</span><span>,</span> <span>middle</span><span>);</span>
<span>right</span> <span>=</span> <span>Arrays</span><span>.</span><span>copyOfRange</span><span>(</span><span>array</span><span>,</span> <span>middle</span><span>,</span> <span>n</span><span>);</span>
<span>import</span> <span>java.util.Arrays</span><span>;</span>
<span>...</span>
<span>// Nice</span>
<span>left</span> <span>=</span> <span>Arrays</span><span>.</span><span>copyOfRange</span><span>(</span><span>array</span><span>,</span> <span>0</span><span>,</span> <span>middle</span><span>);</span>
<span>right</span> <span>=</span> <span>Arrays</span><span>.</span><span>copyOfRange</span><span>(</span><span>array</span><span>,</span> <span>middle</span><span>,</span> <span>n</span><span>);</span>
import java.util.Arrays;
...
// Nice
left = Arrays.copyOfRange(array, 0, middle);
right = Arrays.copyOfRange(array, middle, n);

Enter fullscreen mode Exit fullscreen mode

Then the second is this code. 

<span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>&&</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>if</span><span>(</span><span>left</span><span>[</span><span>leftIndex</span><span>]</span> <span><</span> <span>right</span><span>[</span><span>rightIndex</span><span>])</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
    <span>}</span>
    <span>else</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
    <span>}</span>
<span>}</span>
<span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
<span>}</span>
<span>while</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
<span>}</span>
<span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>&&</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>if</span><span>(</span><span>left</span><span>[</span><span>leftIndex</span><span>]</span> <span><</span> <span>right</span><span>[</span><span>rightIndex</span><span>])</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
    <span>}</span>
    <span>else</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
    <span>}</span>
<span>}</span>

<span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
<span>}</span>
<span>while</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
<span>}</span>
while(leftIndex < leftSize && rightIndex < rightSize) {
    if(left[leftIndex] < right[rightIndex]) {
        array[arrayIndex++] = left[leftIndex++];
    }
    else {
        array[arrayIndex++] = right[rightIndex++];
    }
}

while(leftIndex < leftSize) {
    array[arrayIndex++] = left[leftIndex++];
}
while(rightIndex < rightSize) {
    array[arrayIndex++] = right[rightIndex++];
}

Enter fullscreen mode Exit fullscreen mode

This code aims to sort the array and apply it to the original array, so let’s make it one “while”. 

<span>while</span> <span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>||</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>if</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>&&</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>if</span><span>(</span><span>left</span><span>[</span><span>leftIndex</span><span>]</span> <span><</span> <span>right</span><span>[</span><span>rightIndex</span><span>])</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
        <span>}</span>
        <span>else</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
        <span>}</span>
    <span>}</span>
    <span>else</span> <span>if</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
    <span>}</span>
    <span>else</span> <span>if</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
    <span>}</span>
<span>}</span>
<span>while</span> <span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>||</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>if</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>&&</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>if</span><span>(</span><span>left</span><span>[</span><span>leftIndex</span><span>]</span> <span><</span> <span>right</span><span>[</span><span>rightIndex</span><span>])</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
        <span>}</span>
        <span>else</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
        <span>}</span>
    <span>}</span>
    <span>else</span> <span>if</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
    <span>}</span>
    <span>else</span> <span>if</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
    <span>}</span>
<span>}</span>
while (leftIndex < leftSize || rightIndex < rightSize) {
    if(leftIndex < leftSize && rightIndex < rightSize) {
        if(left[leftIndex] < right[rightIndex]) {
            array[arrayIndex++] = left[leftIndex++];
        }
        else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
    else if(leftIndex < leftSize) {
        array[arrayIndex++] = left[leftIndex++];
    }
    else if(rightIndex < rightSize) {
        array[arrayIndex++] = right[rightIndex++];
    }
}

Enter fullscreen mode Exit fullscreen mode

And this statement is interesting. 

<span>else</span> <span>if</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
<span>}</span>
<span>else</span> <span>if</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
<span>}</span>
<span>else</span> <span>if</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
<span>}</span>
<span>else</span> <span>if</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
<span>}</span>
else if(leftIndex < leftSize) {
    array[arrayIndex++] = left[leftIndex++];
}
else if(rightIndex < rightSize) {
    array[arrayIndex++] = right[rightIndex++];
}

Enter fullscreen mode Exit fullscreen mode

Let’s simplify it 

<span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
<span>}</span>
<span>while</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
<span>}</span>
<span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
<span>}</span>
<span>while</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
    <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
<span>}</span>
while(leftIndex < leftSize) {
    array[arrayIndex++] = left[leftIndex++];
}
while(rightIndex < rightSize) {
    array[arrayIndex++] = right[rightIndex++];
}

Enter fullscreen mode Exit fullscreen mode

Lastly, for the complete code. 

<span>public</span> <span>static</span> <span>void</span> <span>mergeSort</span><span>(</span><span>int</span><span>[]</span> <span>array</span><span>)</span> <span>{</span>
    <span>int</span> <span>n</span> <span>=</span> <span>array</span><span>.</span><span>length</span><span>;</span>
    <span>if</span><span>(</span><span>n</span> <span><=</span> <span>1</span><span>)</span> <span>return</span><span>;</span>
    <span>int</span> <span>middle</span> <span>=</span> <span>(</span><span>n</span> <span>/</span> <span>2</span><span>);</span>
    <span>int</span><span>[]</span> <span>left</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>middle</span><span>];</span>
    <span>int</span><span>[]</span> <span>right</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>n</span> <span>-</span> <span>middle</span><span>];</span>
    <span>left</span> <span>=</span> <span>Arrays</span><span>.</span><span>copyOfRange</span><span>(</span><span>array</span><span>,</span> <span>0</span><span>,</span> <span>middle</span><span>);</span>
    <span>right</span> <span>=</span> <span>Arrays</span><span>.</span><span>copyOfRange</span><span>(</span><span>array</span><span>,</span> <span>middle</span><span>,</span> <span>n</span><span>);</span>
    <span>mergeSort</span><span>(</span><span>left</span><span>);</span>
    <span>mergeSort</span><span>(</span><span>right</span><span>);</span>
    <span>merge</span><span>(</span><span>left</span><span>,</span> <span>right</span><span>,</span> <span>array</span><span>);</span>
<span>}</span>
<span>private</span> <span>static</span> <span>void</span> <span>merge</span><span>(</span><span>int</span><span>[]</span> <span>left</span><span>,</span> <span>int</span><span>[]</span> <span>right</span><span>,</span> <span>int</span><span>[]</span> <span>array</span><span>)</span> <span>{</span>
    <span>int</span> <span>leftIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>rightIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>arrayIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>leftSize</span> <span>=</span> <span>left</span><span>.</span><span>length</span><span>,</span>
        <span>rightSize</span> <span>=</span> <span>right</span><span>.</span><span>length</span><span>;</span>
    <span>while</span> <span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>||</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>if</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>&&</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
            <span>if</span><span>(</span><span>left</span><span>[</span><span>leftIndex</span><span>]</span> <span><</span> <span>right</span><span>[</span><span>rightIndex</span><span>])</span> <span>{</span>
                <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
            <span>}</span>
            <span>else</span> <span>{</span>
                <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
            <span>}</span>
        <span>}</span>
        <span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
        <span>}</span>
        <span>while</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
        <span>}</span>
    <span>}</span>
<span>}</span>
<span>public</span> <span>static</span> <span>void</span> <span>mergeSort</span><span>(</span><span>int</span><span>[]</span> <span>array</span><span>)</span> <span>{</span>
    <span>int</span> <span>n</span> <span>=</span> <span>array</span><span>.</span><span>length</span><span>;</span>
    <span>if</span><span>(</span><span>n</span> <span><=</span> <span>1</span><span>)</span> <span>return</span><span>;</span>

    <span>int</span> <span>middle</span> <span>=</span> <span>(</span><span>n</span> <span>/</span> <span>2</span><span>);</span>
    <span>int</span><span>[]</span> <span>left</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>middle</span><span>];</span>
    <span>int</span><span>[]</span> <span>right</span> <span>=</span> <span>new</span> <span>int</span><span>[</span><span>n</span> <span>-</span> <span>middle</span><span>];</span>

    <span>left</span> <span>=</span> <span>Arrays</span><span>.</span><span>copyOfRange</span><span>(</span><span>array</span><span>,</span> <span>0</span><span>,</span> <span>middle</span><span>);</span>
    <span>right</span> <span>=</span> <span>Arrays</span><span>.</span><span>copyOfRange</span><span>(</span><span>array</span><span>,</span> <span>middle</span><span>,</span> <span>n</span><span>);</span>

    <span>mergeSort</span><span>(</span><span>left</span><span>);</span>
    <span>mergeSort</span><span>(</span><span>right</span><span>);</span>
    <span>merge</span><span>(</span><span>left</span><span>,</span> <span>right</span><span>,</span> <span>array</span><span>);</span>
<span>}</span>

<span>private</span> <span>static</span> <span>void</span> <span>merge</span><span>(</span><span>int</span><span>[]</span> <span>left</span><span>,</span> <span>int</span><span>[]</span> <span>right</span><span>,</span> <span>int</span><span>[]</span> <span>array</span><span>)</span> <span>{</span>
    <span>int</span> <span>leftIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>rightIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>arrayIndex</span> <span>=</span> <span>0</span><span>,</span>
        <span>leftSize</span> <span>=</span> <span>left</span><span>.</span><span>length</span><span>,</span>
        <span>rightSize</span> <span>=</span> <span>right</span><span>.</span><span>length</span><span>;</span>

    <span>while</span> <span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>||</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
        <span>if</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span> <span>&&</span> <span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
            <span>if</span><span>(</span><span>left</span><span>[</span><span>leftIndex</span><span>]</span> <span><</span> <span>right</span><span>[</span><span>rightIndex</span><span>])</span> <span>{</span>
                <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
            <span>}</span>
            <span>else</span> <span>{</span>
                <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
            <span>}</span>
        <span>}</span>
        <span>while</span><span>(</span><span>leftIndex</span> <span><</span> <span>leftSize</span><span>)</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>left</span><span>[</span><span>leftIndex</span><span>++];</span>
        <span>}</span>
        <span>while</span><span>(</span><span>rightIndex</span> <span><</span> <span>rightSize</span><span>)</span> <span>{</span>
            <span>array</span><span>[</span><span>arrayIndex</span><span>++]</span> <span>=</span> <span>right</span><span>[</span><span>rightIndex</span><span>++];</span>
        <span>}</span>
    <span>}</span>
<span>}</span>
public static void mergeSort(int[] array) {
    int n = array.length;
    if(n <= 1) return;

    int middle = (n / 2);
    int[] left = new int[middle];
    int[] right = new int[n - middle];

    left = Arrays.copyOfRange(array, 0, middle);
    right = Arrays.copyOfRange(array, middle, n);

    mergeSort(left);
    mergeSort(right);
    merge(left, right, array);
}

private static void merge(int[] left, int[] right, int[] array) {
    int leftIndex = 0,
        rightIndex = 0,
        arrayIndex = 0,
        leftSize = left.length,
        rightSize = right.length;

    while (leftIndex < leftSize || rightIndex < rightSize) {
        if(leftIndex < leftSize && rightIndex < rightSize) {
            if(left[leftIndex] < right[rightIndex]) {
                array[arrayIndex++] = left[leftIndex++];
            }
            else {
                array[arrayIndex++] = right[rightIndex++];
            }
        }
        while(leftIndex < leftSize) {
            array[arrayIndex++] = left[leftIndex++];
        }
        while(rightIndex < rightSize) {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Enjoy your journey 🙂

原文链接：Merge Sort Algorithm

展开阅读全文
© 版权声明
文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
Java（EN）
# java# programming# algorithms# dsa
喜欢就支持一下吧
点赞8 分享
Little compliments mean so much to me sometimes.
有时候，一点微不足道的肯定，对我却意义非凡
评论 抢沙发

请登录后发表评论

    暂无评论内容

kity的头像-拾光赋
今日剩余 79.6%
本周剩余 54.2%
本月剩余 46.0%
本年剩余 70.9%
最近评论
杀人蜂的头像-拾光赋

杀人蜂3天前0

我很好奇这个网站能提供什么
Vito的头像-拾光赋

Vito6个月前2

你就是我心中的那首忐忑，总是让我惊心动魄
Jason.Meng的头像-拾光赋钻石会员

Jason.Meng徽章-人气大使-拾光赋6个月前2

总是会在人生的不同阶段反复爱上大佬的文章~
每日一言
To do the useful thing, to say the courageous thing, to contemplate the beautiful thing: that’s enough for one man’s life.
做有用的事，说勇敢的话，想美好的事，一生足矣