Merge Sort

Examples

• 3

  Merge Sort Basics

  edit move example delete share

  3

  Merge Sort is a divide-and-conquer algorithm. It divides the input list of length n in half successively until there are n lists of size 1. Then, pairs of lists are merged together with the smaller first element among the pair of lists being added in each step. Through successive merging and through comparison of first elements, the sorted list is built.

  An example:

  

  Time Complexity: T(n) = 2T(n/2) + Θ(n)

  The above recurrence can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is Θ(nLogn). Time complexity of Merge Sort is Θ(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.

  Auxiliary Space: O(n)

  Algorithmic Paradigm: Divide and Conquer

  Sorting In Place: Not in a typical implementation

  Stable: Yes

  edited Oct 12 at 23:07

  

  
• 0

  Merge Sort Implementation in C#

  edit move example delete share

  0

  public class MergeSort
  {
      static void Merge(int[] input, int l, int m, int r)
      {
          int i, j;
          var n1 = m - l + 1;
          var n2 = r - m;
  
          var left = new int[n1];
          var right = new int[n2];
  
          for (i = 0; i < n1; i++)
          {
              left[i] = input[l + i];
          }
  
          for (j = 0; j < n2; j++)
          {
              right[j] = input[m + j + 1];
          }
  
          i = 0;
          j = 0;
          var k = l;
  
          while (i < n1 && j < n2)
          {
              if (left[i] <= right[j])
              {
                  input[k] = left[i];
                  i++;
              }
              else
              {
                  input[k] = right[j];
                  j++;
              }
              k++;
          }
  
          while (i < n1)
          {
              input[k] = left[i];
              i++;
              k++;
          }
  
          while (j < n2)
          {
              input[k] = right[j];
              j++;
              k++;
          }
      }
  
      static void SortMerge(int[] input, int l, int r)
      {
          if (l < r)
          {
              int m = l + (r - l) / 2;
              SortMerge(input, l, m);
              SortMerge(input, m + 1, r);
              Merge(input, l, m, r);
          }
      }
  
      public static int[] Main(int[] input)
      {
          SortMerge(input, 0, input.Length - 1);
          return input;
      }
  }
  

  edited Oct 12 at 23:07