#include <iostream>
#include <cstdlib>
#include <vector>
#include <ctime>

struct Data
{
   int key;
   int original_index;
};

bool compare_with_itself_called = false;
bool pointer_order_changed = false;

int compare(const void *p1, const void *p2)
{
   if(p1==p2)
   {
   	  compare_with_itself_called = true;
   	  return 0;
   }
   const Data *d1 = (const Data*)p1;
   const Data *d2 = (const Data*)p2;
   if(d1->key < d2->key)
     return -1;
   if(d2->key < d1->key)
     return 1;
   bool index_cond = d1->original_index<d2->original_index;
   bool ptr_cond = (p1<p2);
   if(index_cond!=ptr_cond)
   {
   	  pointer_order_changed = true;
   }
   return index_cond ? -1 : 1;
}

void outputArray(Data d[], unsigned n)
{
	for(unsigned i=0; i!=n; ++i)
	   std::cout << d[i].key << "@" << d[i].original_index << std::endl;
}

bool isStableSorted(const std::vector<Data>& d)
{
   size_t n = d.size();
   for(size_t i=1; i<n; ++i)
   {
      if(d[i-1].key==d[i].key &&
         d[i-1].original_index>d[i].original_index)
         return false;
   }
   return true;
}

int main()
{
   srand((unsigned)time(0));
   const unsigned NPASSES = 100000;
   unsigned nStableSorted = 0;
   for(unsigned pass=0; pass<NPASSES; ++pass)
   {
      unsigned N = rand()*1000/RAND_MAX+1;
      unsigned K = N/5+1;
      unsigned M = rand()*K/RAND_MAX+1;
      //
      std::vector<Data> d(N);
      for(unsigned i=0; i<N; ++i)
      {
         d[i].key = rand()*M/RAND_MAX+1;
         d[i].original_index = i;
      }
      //
      qsort(&(d[0]), N, sizeof(Data), compare);
      //
      if(isStableSorted(d))
         ++nStableSorted;
   }
   std::cout << "Total arrays sorted: " << NPASSES << std::endl;
   std::cout << "Stable-sorted arrays: " << nStableSorted << std::endl;
   std::cout << "compare_with_itself_called="
      << (compare_with_itself_called ? "true" : "false") << std::endl;
   std::cout << "pointer_order_changed="
      << (pointer_order_changed ? "true" : "false") << std::endl;
   return 0;
}