StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It seems you actually don't know what merging here means. A merge sort is a divide and conquer algorithm. Here, the conquer part means that you're going to merge two sorted arrays. Thus, to merge them, you always take the lowest item of the two arrays and put it into the next position of the output array, and advancing one position in the array where you took the item from.</p> <p>Take this merge method as a basic example, just to get the idea.</p> <pre><code>public class MergeTest { public static void main(String[] args) { int[] sorted1 = new int[] {2, 5, 6, 8, 10}; int[] sorted2 = new int[] {1, 3, 4, 7, 9}; int[] result = merge(sorted1, sorted2); // returns [1,2,3,4,5,6,7,8,9,10] } public static int[] merge (int[] input1, int[] input2) { int[] output = new int[input1.length + input2.length]; int pos1 = 0; int pos2 = 0; while (pos1 < input1.length && pos2 < input2.length) { int val1 = input1[pos1]; int val2 = input2[pos2]; if (val1 < val2) { output[pos1++ + pos2] = val1; } else { output[pos1 + pos2++] = val2; } } while (pos1 < input1.length) { int val = input1[pos1]; output[pos1++ + pos2] = val; } while (pos2 < input2.length) { int val = input2[pos2]; output[pos1 + pos2++] = val; } return output; } } </code></pre> <p>And here's a little extra: the mergeSort method itself.</p> <pre><code>public static int[] mergeSort (int[] input) { if (input.length == 1) { return input; } int middle = input.length / 2; // divide int[] divided1 = Arrays.copyOfRange(input, 0, middle); int[] divided2 = Arrays.copyOfRange(input, middle, input.length); // conquer int[] sorted1 = mergeSort(divided1); int[] sorted2 = mergeSort(divided2); return merge(sorted1, sorted2); } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload