Does the order of input matter in cross-validation in linear regression? Please imagine the following problem:


*

*A linear regression problem with one input variable (X) and one output (Y)

*The number of input data is 50 instances.

*The input data is sorted in increasing order of output(y)

*In order to do a 2-fold cross validation, we exactly use the first 25 data as fold 1 and the second 25 data as the second fold.


Does sorting the input have any effect on the result of cross validation?
Any idea is appreciated. 
 A: Yes it affects the result. When you do cross validation, you are setting aside some subset of points (Xt:in this case 25 points) to build a hypothetical model and the remainder of points are used for validation(Xv: the remaining 25 points). With two-fold you will do this twice where each set of points has a turn as the training set and as the validation set. The error found in validation is then averaged as an estimate of how well this class of models (linear regression models) will perform when faced with new data.
Now, consider the first model where you only use the 25 points with the lowest Y values to train your model. The model is trained to perform well for the region where Y values are low. You then verify this model with the points with the highest Y value (which are likely very different points). Can you see the issue, here? Both your training and validation data are biased. This will give you a very pessimistic CV estimate. A better approach is to assign the points randomly (without replacement) to each of your two folds. This way there is less bias in both the training data and validation data.
One more thing... 2-fold is pretty low for number of folds. This means your CV error won't estimate the final model's error very well. Each of the two models you build for CV is only using 25 points for training, but the final model will (should) use all 50. This is a big gap. If you used 10-fold, on the other hand, you'd be using 45 for training and only 5 for validation. A model with 45 points should be similar to one with 50, so it's a better estimate of the out-of-sample error. Of course the main drawback is that you have to build 10 models.
A: As ac5 already said, yes this is likely to affect outcome: 


*

*your two models would look at completely disjoint sets of data, and 

*are both tested completely outside their training domain (aka calibration range).


So this setup violates all kinds of assumptions that training, application and test domain are the same.
Nevertheless, testing performance for cases (just) outside the training domain is useful to answer questions about how fast the prediction ability breaks down outside the training domain. But this would be in addition to validation setups that measure the performance for unknown cases coming from the domain the model was trained for.
See also my answer here: https://stats.stackexchange.com/a/69293/4598
