Mysterious Case of iPod Shuffle Always Shuffling

Just recently I experienced something odd. My good old iPod Shuffle seemed to ignore the “play in order” setting on the device and instead elected to do as the name implies and shuffle the songs.
What preceded that sudden change of behavior was a failed attempt to sync with iTunes that actually turned into restoring the firmware of the device. For whatever reason, iTunes detected a problem and its only solution was to wipe the iPod. So I did that and afterwards I had that shuffling play-in-order mode.
What actually happened is that with the restore of the firmware the default sorting of tracks on the device changed to be by their track-id. That means it sounded random to me but was in order for the Pod-thing. To solve my problem I opened the “What’s on my iPod” screen and clicked on the “Name” column to sort by artist name.

I “saved” this setting by syncing and then I was done.