funny i used to say sorry all the time as well, for me i said it because i thought people would like me more. it is possible to retrain your mind i have.
hypnotherapy has helped me work through a lot of issues it might help you.
take care