title: How to implement insertion sort algorithm in C++ with arrays and pointers?
body: <p>I am trying to learn C++, arrays and pointers. I decided to implement the <a href="http://en.wikipedia.org/wiki/Insertion_sort" rel="nofollow noreferrer">insertion sort algorithm</a>. So, here is my code and my wrong output. What should I do to correct it? Can you please tell me what is my mistake and what should I avoid if it is a common error?</p>
  
  <p><strong>My code:</strong></p>
  
  <pre><code>// InsertionSort.cpp
  
  #include "stdafx.h"
  #include &lt;iostream&gt;
  
  int DeclareAnInteger();
  int* DeclareAndShowTheArray(int n);
  int* InsertionSort(int *A, int n);
  
  int main()
  {
  
     int n = DeclareAnInteger();
     int *A;
     A = DeclareAndShowTheArray(n);
     int *B;
     B = InsertionSort(A, n);
  
     system("PAUSE");
     return 0;
  }
  
  int DeclareAnInteger()
  {
     int n;
     std::cout &lt;&lt; "Please enter a positive integer n: ";
     std::cin &gt;&gt; n;
     return n;
  }
  
  int* DeclareAndShowTheArray(int n)
  {
     int *A;
     A = (int *)alloca(sizeof(int) * n);
     for (int i = 0; i &lt; n; i++)
     {
        std::cout &lt;&lt; "Please enter the value of A[" &lt;&lt; i + 1 &lt;&lt; "]: ";
        std::cin &gt;&gt; A[i];
     }
     std::cout &lt;&lt; "The unsorted array is: ";
     for (int i = 0; i &lt; n; i++)
     {
        std::cout &lt;&lt; A[i];
        std::cout &lt;&lt; "\t";
     }
     std::cout &lt;&lt; "\n";
     return A;
  }
  
  int* InsertionSort(int *A, int n)
  {
     int k;
     //int *A = new int[n];
     for (k = 1; k &lt; n; k++)
     {
        int key = A[k];
        int m   = k - 1;
        while (m &gt;= 0 &amp; A[m] &gt; key)
        {
           A[m + 1] = A[m];
           m        = m - 1;
        }
        A[m + 1] = key;
     }
     std::cout &lt;&lt; "The sorted array is: ";
     for (int i = 0; i &lt; n; i++)
     {
        std::cout &lt;&lt; A[i];
        std::cout &lt;&lt; "\t";
     }
     std::cout &lt;&lt; "\n" &lt;&lt; std::endl;
     return A;
  }
  </code></pre>
  
  <p><strong>My output:</strong>
  <img src="https://i.stack.imgur.com/mgYFK.png" alt="enter image description here"></p>