title: Why quick sort is unstable
body: <p>I know there are several similar posts, but none of the answers are satisfying, which is why I want to ask this question again.</p>
  
  <p>Consider the code below. It is my implementation of quick sort according to CRLS Introduction to Algorithms</p>
  
  <pre><code>int partition(int* a, int s, int e)
  {
      int pivot = a[e];
      int q = s-1;
      for (int i = s; i &lt;= e; i++)
      {
          if (a[i] &lt;= pivot) {
              q++;
              int tmp = a[q];
              a[q] = a[i];
              a[i] = tmp;
          }
      }
      return q;
  }
  
  void quickSort(int* a, int s, int e)
  {
      if (e &gt; s) {
          int q = partition(a, s, e);
          quickSort(a, s, q-1);
          quickSort(a, q+1, e);
      }
  }
  </code></pre>
  
  <p>Stable sorting algorithms maintain the relative order of records with equal keys (i.e., values). I don't understand why quick sort is not one of them. Although there are swaps between unadjacent elements in it, but I still don't see why that will cause unstability.
  I really hope someone could give examples to explain this.</p>
  
  <p>Thank you.</p>