I have been looking for ages. hellllp!!!
Sandshrew is located in Wayward Cave in Diamond.
But unfortunately, you must have Pokemon LeafGreen in your GBA slot for this to happen.
If you don't have LeafGreen, you'll have to get it via trade. Sorry!
Source 2 (A bit more trustworthy then the first source)
Source 3: Experience