Objective: To compare conditional random fields (CRF), hidden Markov models (HMMs) and Bayesian linear discriminants (LDs) for cardiorespiratory sleep stage classification on a five-class sleep staging task (wake/N1/N2/N3/REM), to explore the benefits of incorporating time information in the classification and to evaluate the feasibility of sleep staging on obstructive sleep apnea (OSA) patients. Approach: The classifiers with and without time information were evaluated with 10-fold cross-validation on five-, four- (wake/N1 + N2/N3/REM) and three-class (wake/NREM/REM) classification tasks using a data set comprising 443 night-time polysomnography (PSG) recordings of 231 participants (180 healthy participants, 100 of which had a 'regular' sleep architecture, and 51 participants previously diagnosed with OSA). Main results: CRF with time information (CRFt) outperforms all other classifiers on all tasks, achieving a median accuracy and Cohen's κ for all participants of 62.8% and 0.44 for five classes, 68.8% and 0.47 for four classes, and 77.6% and 0.55 for three classes. An advantage was found in training classifiers, specifically for 'regular' and 'OSA' participants, achieving an improvement in classification performance for these groups. For 'regular' participants, CRFt achieved a median accuracy and Cohen's κ of 67.0% and 0.51, 70.8% and 0.53 and 81.3% and 0.62 for five-, four- and three-classes respectively, and for 'OSA' patients, of 59.9% and 0.40, 69.7% and 0.45, and 75.8% and 0.51 for five-, four- and three-classes respectively. Significance: The results suggest that CRFt is not only better at learning and predicting more complex and irregular sleep architectures, but that it also performs reasonably well in five-class classification - the standard for sleep scoring used in clinical PSG. Additionally, and albeit with a decrease in performance when compared with healthy participants, sleep stage classification in OSA patients using cardiorespiratory features and CRFt seems feasible with reasonable accuracy.