text: /**
   * @file
   * @brief Implementation of [merge sort] algorithm
   */
  #include <stdio.h>
  #include <stdlib.h>
  
  /**
   * @addtogroup sorting Sorting algorithms
   * @{
   */
  /** Swap two integer variables
   * @param [in,out] a pointer to first variable
   * @param [in,out] b pointer to second variable
   */
  void swap(int *a, int *b)
  {
      int t;
      t = *a;
      *a = *b;
      *b = t;
  }
  
  /**
   * @brief Perform merge of segments.
   *
   * @param a array to sort
   * @param l left index for merge
   * @param r right index for merge
   * @param n total number of elements in the array
   */
  void merge(int *a, int l, int r, int n)
  {
      int *b = (int *)malloc(n * sizeof(int)); /* dynamic memory must be freed */
      int c = l;
      int p1, p2;
      p1 = l;
      p2 = ((l + r) / 2) + 1;
      while ((p1 < ((l + r) / 2) + 1) && (p2 < r + 1))
      {
          if (a[p1] <= a[p2])
          {
              b[c++] = a[p1];
              p1++;
          }
          else
          {
              b[c++] = a[p2];
              p2++;
          }
      }
  
      if (p2 == r + 1)
      {
          while ((p1 < ((l + r) / 2) + 1))
          {
              b[c++] = a[p1];
              p1++;
          }
      }
      else
      {
          while ((p2 < r + 1))
          {
              b[c++] = a[p2];
              p2++;
          }
      }
  
      for (c = l; c < r - l + 1; c++) a[c] = b[c];
  
      free(b);
  }
  
  /** Merge sort algorithm implementation
   * @param a array to sort
   * @param n number of elements in the array
   * @param l index to sort from
   * @param r index to sort till
   */
  void merge_sort(int *a, int n, int l, int r)
  {
      if (r - l == 1)
      {
          if (a[l] > a[r])
              swap(&a[l], &a[r]);
      }
      else if (l != r)
      {
          merge_sort(a, n, l, (l + r) / 2);
          merge_sort(a, n, ((l + r) / 2) + 1, r);
          merge(a, l, r, n);
      }
  
      /* no change if l == r */
  }
  /** @} */
  
  /** Main function */
  int main(void)
  {
      int *a, n, i;
      scanf("%d", &n);
      a = (int *)malloc(n * sizeof(int));
      for (i = 0; i < n; i++)
      {
          scanf("%d", &a[i]);
      }
  
      merge_sort(a, n, 0, n - 1);
      for (i = 0; i < n; i++)
      {
          printf(" %d", a[i]);
      }
  
      free(a);
  
      return 0;
  }
  