Merge Sort

Examples

• Improvements requested:

  • This was posted as an example, but it does not attempt to illustrate the topic. It should possibly be an edit to the topic, a separate topic, or deleted altogether. –  Peter O. Dec 1 at 4:32

    This post is part of the introduction, not an example.

    add a comment

  Edit Example Delete Example
  4

  Merge Sort Basics

  edit move example delete share 1

  4

  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

  Bottoms-up Java Implementation

  edit move example delete share

  0

      public class MergeSortBU {
      private static Integer[] array = { 4, 3, 1, 8, 9, 15, 20, 2, 5, 6, 30, 70, 60,80,0,9,67,54,51,52,24,54,7 };
  
      public MergeSortBU() {
      }
  
      private static void merge(Comparable[] arrayToSort, Comparable[] aux, int lo,int mid, int hi) {
  
          for (int index = 0; index < arrayToSort.length; index++) {
              aux[index] = arrayToSort[index];
          }
  
          int i = lo;
          int j = mid + 1;
          for (int k = lo; k <= hi; k++) {
              if (i > mid)
                  arrayToSort[k] = aux[j++];
              else if (j > hi)
                  arrayToSort[k] = aux[i++];
              else if (isLess(aux[i], aux[j])) {
                  arrayToSort[k] = aux[i++];
              } else {
                  arrayToSort[k] = aux[j++];
              }
  
          }
      }
  
      public static void sort(Comparable[] arrayToSort, Comparable[] aux, int lo, int hi) {
          int N = arrayToSort.length;
          for (int sz = 1; sz < N; sz = sz + sz) {
              for (int low = 0; low < N; low = low + sz + sz) {
                  System.out.println("Size:"+ sz);
                  merge(arrayToSort, aux, low, low + sz -1 ,Math.min(low + sz + sz - 1, N - 1));
                  print(arrayToSort);
              }
          }
  
      }
  
      public static boolean isLess(Comparable a, Comparable b) {
          return a.compareTo(b) <= 0;
      }
  
      private static void print(Comparable[] array) {http://stackoverflow.com/documentation/algorithm/5732/merge-sort#
          StringBuffer buffer = new StringBuffer();http://stackoverflow.com/documentation/algorithm/5732/merge-sort#
          for (Comparable value : array) {
              buffer.append(value);
              buffer.append(' ');
          }
          System.out.println(buffer);
      }
  
      public static void main(String[] args) {
          Comparable[] aux = new Comparable[array.length];
          print(array);
          MergeSortBU.sort(array, aux, 0, array.length - 1);
      }
  }
  

  edited Dec 2 at 19:21

  
• 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

  

  
• 0

  Merge Sort Implementation in Java

  edit move example delete share

  0

  Below there is the implementation in Java using a generics approach. It is the same algorithm, which is presented above.

  public interface InPlaceSort<T extends Comparable<T>> {
  void sort(final T[] elements); }
  
  
  public class MergeSort < T extends Comparable < T >> implements InPlaceSort < T > {
  
  
  @Override
  public void sort(T[] elements) {
      T[] arr = (T[]) new Comparable[elements.length];
      sort(elements, arr, 0, elements.length - 1);
  }
  
  // We check both our sides and then merge them
  private void sort(T[] elements, T[] arr, int low, int high) {
      if (low >= high) return;
      int mid = low + (high - low) / 2;
      sort(elements, arr, low, mid);
      sort(elements, arr, mid + 1, high);
      merge(elements, arr, low, high, mid);
  }
  
  
  private void merge(T[] a, T[] b, int low, int high, int mid) {
      int i = low;
      int j = mid + 1;
  
      // We select the smallest element of the two. And then we put it into b
      for (int k = low; k <= high; k++) {
  
          if (i <= mid && j <= high) {
              if (a[i].compareTo(a[j]) >= 0) {
                  b[k] = a[j++];
              } else {
                  b[k] = a[i++];
              }
          } else if (j > high && i <= mid) {
              b[k] = a[i++];
          } else if (i > mid && j <= high) {
              b[k] = a[j++];
          }
      }
  
      for (int n = low; n <= high; n++) {
          a[n] = b[n];
      }}}
  

  created Nov 22 at 2:03

  
• 0

  Merge Sort Implementation in Python

  edit move example delete share

  0

  def merge(X, Y):
      " merge two sorted lists "
      p1 = p2 = 0
      out = []
      while p1 < len(X) and p2 < len(Y):
          if X[p1] < Y[p2]:
              out.append(X[p1])
              p1 += 1
          else:
              out.append(Y[p2])
              p2 += 1
      out += X[p1:] + Y[p2:]
      return out
  
  def mergeSort(A):
      if len(A) <= 1:
          return A
      if len(A) == 2:
          return sorted(A)
  
      mid = len(A) / 2
      return merge(mergeSort(A[:mid]), mergeSort(A[mid:]))
  
  if __name__ == "__main__":
      # Generate 20 random numbers and sort them
      A = [randint(1, 100) for i in xrange(20)]
      print mergeSort(A)
  
  

  created Nov 30 at 21:07