No, you can uses the Google Photos app without it being on the cloud. I use it on my phone. I just don't use the cloud version because I find it a tad annoying.
Unfortunately I have had the same issue with Google Play. It just puts the images in whatever order it wishes, then new images (downloaded, installed and photos taken) tend to be listed prior to all others. It usually only gives you the option to list them by locations or time, not by name.
You might try moving them to a computer and then back to the device, copying them in reverse (I have to do this with music on a player, otherwise it lists things all out of order). Or straight forward, different devices different issues.
In the end, you may want to store the images off the device anyway, as to limit the risk of losing them. Due to the device breaking, being stolen, dying, etc.