Excessive long time on quicksorting

I'm using Kruskal's algorithm for minimal cost tree to solve a high school c++ problem.
The graph is represented in an array of arcs. My problem is rather odd: quicksort takes an awful lot of time (17 sec on an AMD Athlon LE-1640 2.59Ghz) sorting the array by its .c member value. What's wrong with my code?
The values i'm testing for are: N(number of nods in the graph) = 500, M(number of arcs in the graph) = 10000.
LE: Solved - The quicksort algorithm's implementation was wrong - the recursive calls should be made outside the while loop.

Code:

 
#include <fstream>

using namespace std;
ifstream i_file("retea.in");
ofstream o_file("retea.out");

#define Nmax 1001
#define Mmax 20001
#define Kmax 50001
struct Conexiune
{
	int x;
	int y;
	double c;
};
void Quicksort(int left, int right, Conexiune Vector[])    //<--takes 17 sec to sort the array
{
	int i = left;
	int j = right;
	Conexiune temp;
	Conexiune pivot = Vector[(i+j)/2];
	while(i<=j)
	{ 
		while(Vector[i].c<pivot.c) i++;
		while(Vector[j].c>pivot.c) j--;
		
		if(i<=j)
		{
			temp = Vector[i];
			Vector[i] = Vector[j];
			Vector[j] = temp;
			i++;
			j--;
		}
         }  //<---Fixed bracket :)
		if(left < j)
		{
			Quicksort(left,j, Vector);
		}
 		if(i<right)
		{
			Quicksort(i, right, Vector);
		}
		
	


	
}


Conexiune Muchie[Mmax];
int N, M, K;
int Familie[Nmax];
int Selectat[Mmax];

int main()
{
	
	int i, j;	
	i_file>>N>>M>>K;
	for(i=0; i<M; i++)
	{
		i_file>>Muchie[i].x>>Muchie[i].y>>Muchie[i].c;
		if(i<N)
		{
			Familie[i+1] = i+1;
		}
		Selectat[i]= 0;
	}
	

	Quicksort(0, M-1,(Conexiune*) Muchie);
	
	i=N-1;
	while(i>0)
	{
		for(j=0; j<M; j++)
		{	

			if(Familie[Muchie[j].x]!=Familie[Muchie[j].y])
			{								
				int min, max;
				
				Selectat[j] = 1;
				if(Familie[Muchie[j].x] < Familie[Muchie[j].y])
				{				
					min = Familie[Muchie[j].x];
					max = Familie[Muchie[j].y];
				}
				else
				{
					max = Familie[Muchie[j].x];
					min = Familie[Muchie[j].y];
				}
				for(int z = 1; z<=N; z++)
				{
					if(Familie[z] == max)
					{
						Familie[z]= min;
					}

				}
				i--;
				if(i<0) break;
			}
		}
	}

	double suma=0;
	double Vector[Kmax];
	int counter = 1;
	int localcounter = 0;
	Vector[0] = 0;
	double max =0;
	for(i=0; i<M; i++)
	{
		if(Selectat[i] == 1)
		suma = suma + Muchie[i].c;
		if(Selectat[i] == 1 && max < K)
		{
			
			localcounter =0;
			for(j=0; j<counter; j++)
			{
				if(Muchie[i].c + Vector[j] > max )
				{

					max = Muchie[i].c + Vector[j];
					Vector[localcounter+counter] = Muchie[i].c + Vector[j];
					localcounter++;
					
				}
			}
			counter = counter + localcounter;
		}

	}
	o_file<<suma<<"\n"<<counter;
	


	return 0;
}

> temp = Vector[i];
> Vector[i] = Vector[j];
> Vector[j] = temp;
The size of your struct (approx 16 bytes) probably means the compiler is generating calls to memcpy() to perform your struct assignments.

Calls to memcpy() for small amounts of memory are expensive in relation to the amount of useful work done.

Profile how many times you actually hit these 3 lines.

It steps 341125075 times (for a 10000 long array) through those 3 lines - this is way past O(n log n) complexity.

Times that large for such a small struct to me make it jump out right away that it cannot simply be inefficiency of individual operations.
Plugging this code directly into my sorting algorithm demo program indicated that it is far worse than O(n*n) running time, and in fact looks somewhat similar in operation to Stooge Sort!
There was clearly some serious algorithmic flaw here in this implementation.

It turns out that the problem is that the recursive calls are being made from inside the loop. These calls need tobe made after the while loop. Fixing that makes it run as expected. So you only had one bracket in the wrong place.

Thanks, that solved the problem.
As to what Salem wrote about memcpy() calls being inefficient for small chunks of data, would it make any noticeable difference to define a custom assignment operator for manually copying each member - my execution time limit is 0.6 sec?

A self-defined operator most likely won't improve efficiency, on the contrary: unnecessary assignments can be optimized away with compiler-generated operator=, but since the compiler doesn't know what your operator= does, it can't optimize it away (who knows, perhaps you increment some global variable, or write a letter to the pope every time operator= is called). Low-level efficiency you can worry about after profiling, anyways. But you might see an essential improvement in your algorithm if you don't blindly take the value in the middle of your array, but take, say, 5 random values and use the median of this sample, and don't recurse if your array has a length of some fixed size, say 10. Or even better, use std::sort(), which is so highly optimized that you won't come near it with home-brew code, most likely. Finally, if you did what you algorithmically could, play around with compiler optimizations before doing dirty work like low-level optimization yourself. It (a) saves your time and (b) preserves readability/maintainability of your code.

No, there is no need to define a custom assignment operator.

Problem solved, the code performs beautifully with a worst execution time of 0.21 sec.