I was looking at some homework and noticed that before building certain types of models (such as non cross validated KNN models) we're told to sort data and other times we're told to shuffle it, i.e. before cross validation, or when splitting data into train/validation/test samples.
Can someone clarify when it's best to shuffle data, and when it's best to leave it sorted?
Pre-treatment
If your data comes from different sources (different sensors, stores...) and you want to split it into train/validation sets, yes it is generally safer to shuffle it, as the partitions you will create will come from different sources.
Say some patients come from various hospitals and you want to predict if they have a specific disease from the following variables : age, sex, location. You gathered data from various hospitals and one of them, hospital $i$, is specialized in treating this disease. Then, if you just stacked the lines, you will see that lines between 100 and 150 (corresponding to the observations of hospital $i$) are more likely to be affected that other and treat it as a relevant predictor. You don't want this to happen. Even worse could be to train your model on this specific hospital data set and test it on another.
Training and performance
If you concern is based on training only, the performance of batch methods should not be influenced by the order of the rows.
Take the example of a linear regression: $$\hat\beta=(X'X)^{-1}X'Y$$If you multiply $X$ by a permutation matrix $O$ such that $X_2=OX$ contains the same lines as $X$ in a different order, then, using the fact that $O'O=I$ $$\hat\beta=(X_2'X_2)^{-1}X_{2}'Y_2$$
It is the same for the other batch methods. KNN, in particular, in its original implementation is not dependent on the order of the rows.
However, note that some machine learning method rely on various subsets of the data (random forests, gradient boosting methods) the order may lead to different performances (though the difference should not be important).
The specific case of online learning
When it comes to online learning the answer is not obvious. Shuffling the data removes possible drifts. Maybe you want to take them into account in your model, maybe you don't. Regarding this last point, there is no specific answer. Drift should probably be removed if your data does not have a natural order (does not depend on time per example). If it arrives in a chronological fashion, you may want to try your model with and without possible drift.
