## Definition

Merge sort sorts an array based on a divide, conquer, and combine strategy. We know that an array of size one is always sorted. We also know that it is trivial to combine two already sorted arrays into one larger array (merge). We can therefore recursively **divide** the array in half until we reach arrays of size one. Since they are sorted we can consider them **conquered** because they are sorted. We can now **combine** them to complete the sorted array.

## Code

public static void main(String[] args) { int[] a = {1,3,6,3,4,8}; fullMerge(a); System.out.print(Arrays.toString(a)); } public static int[] sort (int[] a){ if (a.length <= 1){ return; } else{ int[] left = new int[a.length /2]; int[] right = new int[a.length - a.left]; System.array.copy System.array.copy } sort(left); sort(right); merge (a, left, right); } public static int[] merge(int[] x, int[] y) { int[] a = new int[x.length + y.length]; int left = 0; int right = 0; for (int i = 0; i < a.length; i++) { if (left >= x.length){ for (int j = i; j < a.length; j++) { a[j] = y[right]; right++; } return a; } else if (right >= y.length) { for (int j = i; j < a.length; j++) { a[j] = x[left]; left++; } return a; } else if (x[left] < y[right]) { z[i] = x[left]; left++; } else { z[i] = y[right]; right++; } } return a; }

** Not yet done.

## Algorithm

- Divide your unsorted array in two

- Keep on dividing your arrays until each are of length 1

- Start putting the arrays together in the opposite order. Check to see if the first number in one array is smaller than the first in the other. Whichever is smaller set the first number in the combined array to it and go to the next digit in which you placed in the array and repeat until the array is finished. Once one array is completed fill in the rest of the numbers with the other array.