Merge sort is another popular version of the divide and conquer algorithm. It is a very efficient, general-purpose sort algorithm. The algorithm gets is named from the fact that it divides the collection in half, recursively sorts each half, and then merges the two sorted halves back together. Each half of the collection is repeatedly halved until there is only one object in the half, at which point it is sorted by definition. As each sorted half is merged, the algorithm compares the objects to determine where to place each sub set.

As far as divide and conquer algorithms are concerned, merge sort is one of the most efficient algorithms. The algorithm has a worst-, average- and best- case complexity of O(n log(n)), making it an improvement over quick sort even in the worst circumstances.

C#

    public void MergeSort(int[] values, int left, int right) 
    { 
      if (left == right) 
        return; 
 
      if (left < right) 
      { 
     ...