title: Calculate Execution Times in Sort algorithm
body: <p>I implemented Merge Sort and Quick Sort in C++, and I wanna get the execution times using each of two with many of cases those are already Sorted or not &amp; has different size.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;ctime&gt;
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  
  using namespace std;
  
  void Merge(vector&lt;int&gt;&amp; s, int low, int mid, int high) {
      int i = low;
      int j = mid + 1;
      int k = low;
      vector&lt;int&gt; u(s);
  
      while (i &lt;= mid &amp;&amp; j &lt;= high) {
          if (s.at(i) &lt; s.at(j)) {
              u.at(k) = s.at(i);
              i++;
          } else {
              u.at(k) = s.at(j);
              j++;
          }
          k++;
      }
      if (i &gt; mid) {
          for (int a = j; a &lt; high + 1; a++) {
              u.at(k) = s.at(a);
              k++;
          }
      } else {
          for (int a = i; a &lt; mid + 1; a++) {
              u.at(k) = s.at(a);
              k++;
          }
      }
      for (int a = low; a &lt; high + 1; a++)
          s.at(a) = u.at(a);
  }
  
  void MergeSort(vector&lt;int&gt;&amp; s, int low, int high) {
      int mid;
      if (low &lt; high) {
          mid = (low + high) / 2;
          MergeSort(s, low, mid);
          MergeSort(s, mid + 1, high);
          Merge(s, low, mid, high);
      }
  }
  
  void swap(int&amp; a, int&amp; b) {
      int tmp = a;
      a = b;
      b = tmp;
  }
  
  void Partition(vector&lt;int&gt;&amp; s, int low, int high, int&amp; pvpoint) {
      int j;
      int pvitem;
  
      pvitem = s.at(low);
      j = low;
      for (int i = low + 1; i &lt;= high; i++) {
          if (s.at(i) &lt; pvitem) {
              j++;
              swap(s.at(i), s.at(j));
          }
          pvpoint = j;
          swap(s.at(low), s.at(pvpoint));
      }
  }
  
  void QuickSort(vector&lt;int&gt;&amp; s, int low, int high) {
      int pvpoint;
      if (high &gt; low) {
          Partition(s, low, high, pvpoint);
          QuickSort(s, low, pvpoint - 1);
          QuickSort(s, pvpoint + 1, high);
      }
  }
  
  int main() {
      vector&lt;int&gt; CaseSize(20);
  
      for (int i = 0; i &lt; 10; i++) { //10 Arrays those are sorted
          CaseSize.at(i) += (i + 1) * 500;
      }
  
      for (int i = 10; i &lt; 20; i++) { //rest 10 those are not sorted
          CaseSize.at(i) += (i + 1) * 5000;
      }
  
      cout &lt;&lt; "------------------Sorted------------------\n\n";
      cout &lt;&lt; "      Quick Sort       Merge Sort\n";
      for (int i = 0; i &lt; 10; i++) {
          vector&lt;int&gt; Arr(CaseSize.at(i));
          Arr.front() = rand() % Arr.size();
          for (int j = 1; j &lt; Arr.size(); j++) {
              Arr.at(j) = ((17 * Arr.at(j - 1) + 43) % (Arr.size() * 5));
          }
          vector&lt;int&gt; Arr2(Arr);
  
          sort(Arr.begin(), Arr.end());
          sort(Arr2.begin(), Arr2.end());
  
          cout &lt;&lt; "N : " &lt;&lt; CaseSize.at(i) &lt;&lt; "    ";
          clock_t start = (int)clock();
          QuickSort(Arr, 0, Arr.size() - 1);
          printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
          cout &lt;&lt; "\t\t";
  
          clock_t start2 = (int)clock();
          MergeSort(Arr2, 0, Arr2.size() - 1);
          printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
          cout &lt;&lt; endl;
      }
      cout &lt;&lt; endl;
      cout &lt;&lt; "------------------Random------------------\n\n";
      cout &lt;&lt; "        Quick Sort     Merge Sort\n";
      for (int k = 10; k &lt; 20; k++) {
          vector&lt;int&gt; Arr(CaseSize.at(k));
          Arr.front() = rand() % Arr.size();
          for (int l = 1; l &lt; Arr.size(); l++) {
              Arr.at(l) = ((17 * Arr.at(l - 1) + 43) % (Arr.size() * 5));
          }
          vector&lt;int&gt; Arr2(Arr);
  
          cout &lt;&lt; "N : " &lt;&lt; CaseSize.at(k) &lt;&lt; "    ";
  
          clock_t start = (int)clock();
          QuickSort(Arr, 0, Arr.size() - 1);
          printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
  
          cout &lt;&lt; "\t\t";
  
          clock_t start2 = (int)clock();
          MergeSort(Arr2, 0, Arr2.size() - 1);
          printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
          cout &lt;&lt; endl;
      }
      return 0;
  }
  </code></pre>
  
  <p>Well, the program worked actually, but the execution time printed was not like what I expected.
  Did I do all right? I wanna run both algorithms to show their execution times and so I could compare their <strong>TIME COMPLEXITY</strong> in this way (without fixing sort algorithm as much as possible).</p>