Merge sort

The merge-sort algorithm can be described as follows: The algorithm divides the array into two halves and applies a merge sort on each half recursively. After the two halves are sorted, the algorithm then merges them.

Merge sort algorithm

2 public static void mergeSort (int[ ] list) { 3 if (list . length > 1) { 4 mergeSort (list[0 ... list . length / 2) ; 5 mergeSort (list [list . length / 2 + 1 ... list. length]) ; merge list[0 ... list . length / 2] with list [list. length / 2 + 1 .. list. length]; Merge sort employs a divide-and-conquer approach to sort the array. 2 9 5 4 8 1 6 7 split 2 9 5 4 8 1 6 7 split divide 2 9 5 4 8 1 6 7 split 21 19 5 4 8 6 merge 219 45 1 8 6 7 merge conquer 2 459 1 6 7 8 merge 1 2 4 5 6 7 8 9