CareerCup

How can this be NP-complete? If I understood the problem statement correctly then the problem is "easy". If the entire file can fit in memory then the records can be sorted using any standard sorting algorithm. Otherwise the file can still be sorted using any external sorting algorithm. We just have to sort using the second field of each record.

So pseudopolynomial time alg?

struct row_struct
{
	char *data; //for saving second colomn
	long pos; // for saving position of row;
}
->Read file
->sort array of above struct with data O(Nlog(N));
->then print sorted rows using pos.

@RAM, what do you mean?
Sort "positions" into the file (line positions) ?
And why char *data for the second/ field (they are just small integers)?

If you are sorting positions of records in the original file, once you sort these structures, you might have to seek all around the file to actually print the results.

Y?