Conventional sleep analysis relies primarily on electroencephalogram (EEG) waveform features assessed in concert with eye movements, respiration and muscle tone. We explore a complementary "complexity domain" approach based on multiscale entropy (MSE) analysis of EEG signals and discuss its relationships to standard sleep analysis and to that based on electrocardiogram (ECG)-derived cardiopulmonary coupling (CPC). We observe a progressive decrease in complexity associated with decreased arousability, as measured by both conventional sleep scoring and CPC analysis. Furthermore, complexity analysis supports the contention that stage 2 non-REM sleep has distinct sub-phases that map to CPC high- and low-frequency coupled dynamics.