Pfew, that could prove to be a tall order. My guess would be looking for a program that allows A. to change the tags, and B. moves those files to the right folders. I believe iTunes did that for me back in the day. Not sure if other media players can do the same thing.
I guess you can also do it manually. But it depends a lot on the filenames of your files. If they go like artist - track.mp3. Then you could create a folder with said artist's name and move the relevant files there. But if they have names like Johndoe.mp3, then it could become quite impossible.
I'll have a look if I can find a program that works on Linux. Never gotten iTunes to run on Linux through Wine. I'm now using Foobar through Wine. And that one works pretty well. Editing tags is very fast, but I haven't found an option to move the files while tagging them.
If it's just about the tagging of the files, any player with tagging capabilities will do. Or use a program like Easytag. It's in the Mint repos
Enter stuff like artist, track name, album, genre etc. in it, and have the files import to your music player. And you can easily sort stuff from there on