[Android] Shuffle on big playlists is problematic

[CashEclipse]

When playing my 1300 song playlist of downloaded tracks on shuffle with my Lenovo tablet the algorithm only uses the first 50 or so songs from the list to shuffle. Smaller Playlists with ~400 songs work fine. I already reinstalled the app with no further effect. My phone and the desktop app work perfectly fine with it though my phone had the same problem some time ago but then a reinstall helped.

I use a Lenovo Tab 2 A7 running Android 5.0.

Spotify is on version 8.4.24.871 (current) which is the same as on my phone.

Anybody got an idea?