I usually wear shoes, but sometimes, especially morning and evening short walks, I prefer sandals. What I noticed is that if I keep the sandals out, it bends and deforms. What kind of sandals I should use which can withstand the heat in places like middle-east ?
I am not sure what sandals you are talking about (I live in Kuwait where the temperature today is a nice and cool 43C); here we wear all manners of sandals.
The traditional sandals are made of leather or other typical shoe material; what I mean here is that there is no special formula or material used just to avoid the heat.
You should, however, avoid shoes that have cork or perforated wooden soles. These will (especially in Doha and Dubai due to the humidity) crack and in some cases completely disintegrate if you were to walk from a cold apartment onto a hot walkway. This actually happened to a friend.
All shoes deform (except maybe those wooden clogs), this is just due to the natural wear on them from your feet.
However, if your shoes are deforming to the point that they are curling up so that you are unable to use them, this is a fault in the composite material your shoes are made of.
In Dubai you'll find that people wear everything from jogging/walking shoes from sports manufacturers like Nike, all the way to flip flops made of nothing but two pieces of plastic.