Faits: A. Par contrat du 26 octobre 2007, Y._ SA, qui a son siège à ... (Vaud) et qui exploite des pharmacies, a engagé X._, alors domicilié au Locle (Neuchâtel), en qualité d'avocat/juriste/contrôleur/directeur administratif pour un salaire mensuel brut de 11'750 fr., auquel s'ajoute une gratification de fin d'année correspondant au dernier salaire mensuel perçu. Par la suite, le salaire mensuel brut de X._ a été augmenté à 13'750 fr. dès le 1er janvier 2009, puis à 14'300 fr. dès le 1er juillet 2009, un treizième salaire remplaçant dès lors la gratification. Par ailleurs, il recevait des frais mensuels de représentation de 700 fr. et disposait d'une voiture de fonction qu'il pouvait utiliser pour son usage privé. Y._ SA a été rachetée par Z._ AG le 1er juillet 2009. Cette dernière gère plusieurs chaînes de pharmacies, soit A._, B._, C._ et D._. A cette époque, X._ s'occupait pour Y._ SA à la fois du service juridique, des baux commerciaux et des ressources humaines. Le rachat par un groupe aussi important que Z._ impliquait que la répartition des tâches soit repensée. Il a été retenu qu'une nouvelle structure a été peu à peu mise en place. Des négociations se sont ouvertes avec X._ en vue de redéfinir son poste. Le 30 août 2010, il a été informé que les ressources humaines seraient regroupées sous la direction de V._ qui effectuait déjà ce travail pour Z._ depuis 2001. Quant aux baux commerciaux, ils devaient être intégrés dans l'unité " développement ". Il a été proposé à X._ de travailler à Berne comme avocat/juriste sous les ordres de W._, qui exerçait cette activité pour Z._ depuis 2001. X._ a exprimé sa déception, en relevant qu'il avait obtenu l'accord de son employeur pour une formation universitaire en ressources humaines à Genève de septembre 2010 à mai 2011. Il a soumis par la suite son propre projet de contrat de travail, qui n'a pas été accepté. Finalement, une réunion a eu lieu le 13 septembre 2010. Il a été proposé à X._ un projet de contrat de travail en qualité de " Spécialiste Service juridique du groupe Z._ SA, Membre de la direction " avec un salaire annuel de base s'élevant à 13 x 13'300 fr., auquel s'ajoute un bonus (entièrement variable, de 18'200 fr., garanti dans sa totalité pour 2011). X._ a décliné cette offre. Par lettre envoyée le même jour, Y._ SA a résilié le contrat de travail de X._ pour le 31 décembre 2010. Il était précisé qu'il devait transmettre tous ses dossiers au plus tard le 30 septembre 2010 et qu'il était ensuite libéré de l'obligation de travailler, avec la précision qu'il devait prendre pendant cette période un éventuel solde de vacances. X._ a fait parvenir à son employeur un certificat médical attestant de son incapacité totale de travailler du 15 au 23 septembre 2010. Le 6 décembre 2010, X._ a écrit à Z._ SA qu'il acceptait la proposition de contrat de travail faite le 13 septembre 2010. Il lui a été répondu que ce projet avait été refusé par lui et que son revirement était considéré comme une nouvelle offre, laquelle était déclinée. X._ a adressé à son employeur un certificat médical établissant son incapacité totale de travailler du 23 décembre 2010 au 5 janvier 2011. Il a soutenu que la résiliation de son contrat de travail revêtait un caractère abusif. B. Par acte déposé le 5 septembre 2011 au greffe du Tribunal civil du Littoral et du Val-de-Travers, X._ a formé une demande en paiement dirigée contre Y._ SA, concluant à ce que cette dernière soit condamnée à lui verser la somme nette de 61'514 fr. et la somme brute de 30'450 fr. avec intérêts à 5% dès le 1er avril 2011, avec suite de frais et dépens. Y._ SA a conclu au rejet de la demande sous suite de frais et dépens. Par jugement du 30 mars 2012, le Tribunal civil du Littoral et du Val-de-Travers a condamné Y._ SA à verser à X._ la somme de 21'600 fr.85 bruts et 58'800 fr. nets avec intérêts à 5% dès le 1er avril 2011, statuant par ailleurs sur les frais et dépens. Y._ SA a appelé de ce jugement, concluant au déboutement de sa partie adverse. L'intimée a conclu à la confirmation du jugement attaqué. Par arrêt du 19 novembre 2012, la Cour d'appel civile du Tribunal cantonal neuchâtelois a annulé le jugement attaqué et rejeté la demande formée par X._, statuant par ailleurs sur les frais et dépens. C. X._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt cantonal du 19 novembre 2012. Invoquant une violation des art. 310 let. b CPC, 9 Cst., 336, 322 et 329 CO, il conclut, sous suite de frais et dépens, à l'annulation de l'arrêt attaqué et à ce que sa partie adverse soit condamnée à lui payer la somme brute de 21'700 fr.85 et la somme nette de 58'800 fr., dans les deux cas avec intérêts à 5% dès le 1 er avril 2011. L'intimée a conclu au rejet du recours sous suite de frais et dépens. 