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 <ref-law>, 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.

Considérant en droit:
1.
1.1. Interjeté par la partie qui a succombé dans ses conclusions en paiement et qui a donc qualité pour recourir (<ref-law>), dirigé contre un arrêt final (<ref-law>) rendu en matière civile (<ref-law>) par un tribunal supérieur statuant sur recours en dernière instance cantonale (<ref-law>), dans une affaire pécuniaire dont la valeur litigieuse atteint le seuil de 15'000 fr. requis en matière de droit du travail (<ref-law>), le recours est recevable, puisqu'il a été déposé dans le délai (art. 46 al. 1 let. c, 48 al. 1 et 100 al. 1 LTF) et la forme (<ref-law>) prévus par la loi.
1.2. Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Il peut donc également être formé pour violation d'un droit constitutionnel (<ref-ruling> consid. 2.1 p. 247; <ref-ruling> consid. 2.4 p. 313).
Le Tribunal fédéral applique d'office le droit dont il peut contrôler le respect (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.3 p. 336; <ref-ruling> consid. 4 p. 317 s.). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (<ref-law>), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent, lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 1.3 p. 584; <ref-ruling> consid. 2.2.1 p. 389; <ref-ruling> consid. 1.4 p. 400).
Par exception à la règle selon laquelle il applique le droit d'office, le Tribunal fédéral ne peut entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (<ref-law>).
1.3. Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 5.1 p. 356) - ou en violation du droit au sens de l'<ref-law> (<ref-law>).
La partie recourante qui entend s'écarter des constatations de l'autorité précédente doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (ATF <ref-ruling> consid. 5.1 p. 356; <ref-ruling> consid. 1.2 p. 187). La partie recourante qui se plaint d'arbitraire dans l'appréciation des preuves et l'établissement des faits doit motiver son grief d'une manière qui réponde aux exigences de l'<ref-law> (<ref-ruling> consid. 4.1.2 p. 62). Une rectification de l'état de fait ne peut être demandée que si elle est de nature à influer sur le sort de la cause (<ref-law>). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
1.4. Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (<ref-law>). Toute conclusion nouvelle est irrecevable (<ref-law>).
2.
2.1. Constatant que la cour cantonale n'a pas retenu le même état de fait que le juge de première instance, le recourant se plaint d'une violation de l'<ref-law>.
L'<ref-law>, comme cela ressort clairement de son texte, régit les motifs que la partie appelante peut faire valoir à l'appui de son appel. Cette disposition ne concerne en rien le pouvoir d'examen de la cour d'appel. Saisie d'un appel, la cour cantonale dispose d'un pouvoir de cognition complet et revoit librement aussi bien les questions de fait que les questions de droit ( NicolasJeandin, in Code de procédure civile commenté, 2011, n° 5 ad intro art. 308-334 CPC et n° 6 ad <ref-law>; Reetz/Theiler, in Kommentar zur schweizerischen Zivilprozessordnung, Sutter-Somm/Hasenböhler/Leuenberger (éd.), 2010, no 6 ad <ref-law>). L'<ref-law> n'interdit nullement à la cour cantonale d'apprécier à nouveau les preuves apportées et de parvenir à des constatations de fait différentes de celles de l'autorité de première instance. L'<ref-law> ne prescrit pas non plus comment le juge doit apprécier les preuves et sur quelles bases il peut se forger une opinion. Que la cour cantonale ait retenu un état de fait différent de celui admis par le juge de première instance ne saurait donc constituer une violation de l'<ref-law>.
Le Tribunal fédéral ne peut revoir l'appréciation des preuves et l'établissement des faits par la cour cantonale que sous l'angle restreint de l'arbitraire (art. 9 Cst.).
S'agissant de l'appréciation des preuves et de l'établissement des faits, la décision attaquée n'est arbitraire que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, s'il a omis, sans raison sérieuse, de tenir compte d'un moyen important propre à modifier la décision attaquée ou encore si, sur la base des éléments recueillis, il a fait une déduction insoutenable (<ref-ruling> consid. 4.2 p. 560; <ref-ruling> consid. 2.1 p. 9).
La partie recourante qui invoque l'arbitraire dans l'appréciation des preuves et l'établissement des faits doit démontrer par une argumentation précise, en se référant si possible à des pièces indiscutables du dossier, que la cour cantonale a retenu ou omis un fait pertinent d'une manière insoutenable (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 2.2 p. 246). Il ne suffit pas que la partie recourante oppose sa propre version des faits à celle retenue par la cour cantonale ou encore qu'elle tire du dossier quelques éléments favorables à sa thèse; elle doit réussir à démontrer, par des références précises à des moyens de preuve indiscutables, que la position prise par la cour cantonale est insoutenable; ce n'est qu'à cette condition que l'état de fait cantonal peut être considéré comme arbitraire.
Or, en l'espèce, on ne voit pas que le recourant ait réussi à faire une telle démonstration.
2.2. Le recourant soutient que la résiliation de son contrat de travail par l'employeur revêtait un caractère abusif et que la cour cantonale, en le déniant, a violé l'<ref-law>.
Selon l'<ref-law>, le contrat de travail conclu pour une durée indéterminée peut être résilié par chacune des parties. En droit suisse du travail, la liberté de la résiliation prévaut, de sorte que, pour être valable, un congé n'a en principe pas besoin de reposer sur un motif particulier (<ref-ruling> consid. 2.3 p. 514; <ref-ruling> consid. 2.1 p. 116; <ref-ruling> consid. 4.1 p. 538).
Le droit de chaque cocontractant de mettre unilatéralement fin au contrat est toutefois limité par les dispositions sur le congé abusif (<ref-law>) (<ref-ruling> consid. 2.3 p. 514; <ref-ruling> consid. 2.1 p. 116; <ref-ruling> consid. 4.1 p. 538).
L'art. 336 al. 1 et 2 CO énumère des cas dans lesquels la résiliation est abusive. En l'espèce, le recourant ne prétend pas que l'on se trouve dans l'une de ces hypothèses. Cette liste n'est toutefois pas exhaustive et une résiliation abusive peut aussi être admise dans d'autres circonstances; il faut cependant que ces autres situations apparaissent comparables, par leur gravité, aux cas expressément envisagés par l'<ref-law> (<ref-ruling> consid. 2.3 p. 514 s.; <ref-ruling> consid. 2.1 p. 116 s.; <ref-ruling> consid. 4.2 p. 538).
Ainsi, un congé peut être abusif en raison de la manière dont il est donné, parce que la partie qui donne le congé se livre à un double jeu contrevenant de manière caractéristique au principe de la bonne foi, lorsqu'il est donné par un employeur qui viole les droits de la personnalité du travailleur, quand il y a une disproportion évidente des intérêts en présence ou lorsqu'une institution juridique est utilisée contrairement à son but (<ref-ruling> consid. 2.3 p. 515 et les arrêts cités). Pour dire si un congé est abusif, il faut se fonder sur son motif réel (<ref-ruling> consid. 2.3 p. 515). Déterminer le motif d'une résiliation est une question de fait (<ref-ruling> consid. 2.3 p. 515; <ref-ruling> consid. 4.3 p. 540).
Que l'employeur ait eu un comportement incorrect ou qu'il ait brusquement changé d'avis n'implique pas encore que le congé est abusif (ATF <ref-ruling> consid. 4.2 p. 539).
En l'espèce, la cour cantonale a retenu, sur la base de plusieurs déclarations, que la mise en place de la nouvelle structure s'est faite progressivement après le rachat de l'intimée. Le recourant ne parvient pas à démontrer que cette constatation serait arbitraire. On ne peut donc pas constater - comme le suggère le recourant - que l'intimée avait d'emblée l'intention de se séparer de lui et qu'elle a joué à son égard un double jeu. Il apparaît bien que les fonctions exercées par le recourant étaient hétéroclites (le service juridique, les baux commerciaux et les ressources humaines). Il était logique, dans un groupe plus vaste, que l'on tende vers une certaine spécialisation. L'employeur semble avoir recherché de bonne foi une solution pour conserver le recourant à son service, tenant compte de sa formation d'avocat. On ne voit pas, dans cette démarche, en quoi consisterait la mauvaise foi. Quant au fait que le recourant a été autorisé à suivre des cours de ressources humaines, il semble que ce soit à sa demande et que cette autorisation lui soit entièrement favorable, puisqu'il pouvait fréquenter ces cours sur ses heures de travail et aux frais de l'entreprise, tout en améliorant son curriculum vitæ pour la suite de sa carrière, que ce soit à l'intérieur de la même entreprise ou d'une autre. Certes, le recourant pouvait espérer, à la suite de cette décision, qu'il resterait dans le domaine des ressources humaines. Aucune garantie ne lui a cependant été donnée dans ce sens et la décision qui a été prise en définitive, à savoir de confier ce service à une personne qui s'en occupait depuis plus longtemps que lui, paraît logique. Que l'employeur n'ait pas d'emblée pris une position claire ou qu'il ait même changé d'avis ne suffit cependant pas, au vu de la jurisprudence rappelée ci-dessus, à fonder la mauvaise foi. Pour établir le double jeu, le recourant se fonde sur un état de fait qui n'est pas celui retenu par la cour cantonale et qui lie le Tribunal fédéral dès lors que l'arbitraire n'a pas été démontré (art. 105 al. 1 et 2 LTF).
2.3. Pour tenter d'établir le caractère abusif du congé (<ref-law>), le recourant soutient qu'il a été victime d'un " congé-modification ".
En principe, le congé donné parce que le travailleur refuse une modification du contrat de travail n'est pas abusif, sauf si l'employé est licencié parce qu'il n'a pas accepté des modifications qui devaient être immédiatement applicables, lorsque la décision sert de moyen de pression pour imposer une modification du contrat défavorable au travailleur ou encore lorsqu'elle est signifiée à l'employé parce que celui-ci refuse de conclure un nouveau contrat qui viole la loi, une convention collective ou un contrat-type applicable (arrêt 4A_349/2009 du 20 octobre 2009 consid. 3.2; arrêt 4C.282/2006 du 1er mars 2007 consid. 4.2).
En l'espèce, le rachat de l'employeur par un ensemble plus vaste a rendu nécessaire une restructuration de l'entreprise. L'employeur a donc proposé au recourant un nouveau contrat de travail qui déterminait, de façon nouvelle, l'objet de son activité, le salaire et le lieu de travail. Le recourant était évidemment libre d'accepter ou de refuser le nouveau contrat qui lui était proposé. En cas de refus, il devait s'attendre à ce que son contrat de travail soit résilié en respectant le délai de congé et le terme d'échéance. Le congé ne serait abusif, en vertu de la jurisprudence déjà citée, que s'il poursuivait un but contraire au droit. Tel n'est pas le cas en l'espèce. L'employeur n'a pas utilisé l'arme de la résiliation par exemple pour imposer au travailleur une diminution de salaire avant l'échéance; il n'a pas davantage donné congé parce que le travailleur refusait un nouveau contrat qui violait la loi, une convention collective ou un contrat-type applicable. L'arme de la résiliation n'a pas non plus été utilisée pour faire pression sur le travailleur afin qu'il accepte un contrat plus défavorable. En effet, travailler pour un service juridique plus important pouvait compenser la perte d'autres secteurs d'activité (les ressources humaines et les baux commerciaux); que le recourant n'ait pas pu être le directeur de ce service plus important ne saurait être considéré comme une rétrogradation, puisqu'il ne pouvait prétendre passer devant un employé qui était à ce poste depuis plus longtemps que lui. La rémunération proposée était largement équivalente. Pour une personne domiciliée au Locle, se rendre à St-Sulpice ou à Berne apparaît plus ou moins équivalent. On ne voit donc pas que l'on ait voulu lui jouer un mauvais tour. Ainsi, les conditions d'un congé de modification à caractère abusif ne sont pas réunies.
Dans ce contexte, on ne voit pas où le recourant veut en venir lorsqu'il parle d'un délai de réflexion insuffisant. Il ne ressort pas de l'état de fait cantonal qu'il aurait demandé un délai pour réfléchir et que ce délai lui aurait été refusé. Le recourant ne le prétend d'ailleurs même pas. On ne voit pas non plus ce que le recourant voudrait tirer de la dualité juridique entre l'intimée d'une part et le groupe qui l'a rachetée d'autre part. Dès lors que le poste occupé par le recourant chez l'intimée disparaissait à la suite de la restructuration, il était logique de lui proposer un nouveau contrat à conclure avec le groupe qui avait racheté l'intimée. On ne saurait en déduire que l'intimée avait une obligation juridique de conserver indéfiniment à son service le recourant, alors que son poste n'avait plus d'utilité pour l'entreprise.
2.4. Le recourant soutient, invoquant une violation de l'<ref-law>, qu'une augmentation de salaire de 400 fr. par mois lui avait été accordée.
Savoir s'il y a eu des manifestations de volonté concordantes des parties sur ce point est une pure question de fait.
La cour cantonale a analysé les documents produits et les déclarations recueillies. Elle est parvenue à la conclusion que le document produit par le recourant contenait des propositions d'augmentation de salaire préparées par lui-même. Il est évident (en raison de l'interdiction des contrats avec soi-même) que le recourant ne pouvait pas représenter l'employeur pour s'octroyer une hausse de salaire. Un responsable, qui n'avait qu'une signature collective à deux, a signé le document pour exprimer son accord, mais il a admis qu'il avait fait une erreur et qu'il ne pouvait pas en décider seul, ni engager la société par sa seule signature. On ne discerne à ce sujet aucune violation de l'<ref-law>, puisque le second alinéa de cette disposition permet expressément de faire inscrire au registre du commerce une représentation commune de la société. Dès lors que le responsable en question n'avait pas le pouvoir de représenter seul la société, sa signature n'a aucun effet juridique. La cour cantonale a encore constaté que le recourant n'avait émis aucune réclamation quant à son salaire pour l'année 2010 avant la lettre de son avocat du 24 janvier 2011. Cette absence de protestation pendant une si longue période peut être interprétée sans arbitraire comme la preuve que le recourant savait qu'aucun accord des parties n'était intervenu au sujet de cette augmentation de 400 fr. Le fardeau de la preuve incombant au recourant (<ref-law>), on ne saurait dire que la cour cantonale a statué arbitrairement en concluant qu'il n'était pas prouvé que les parties s'étaient mises d'accord sur une augmentation de salaire de 400 fr. par mois.
2.5. Invoquant une violation de l'<ref-law>, le recourant conteste l'opinion de la cour cantonale selon laquelle il pouvait prendre son solde de vacances durant le délai de résiliation.
Le principe de l'obligation d'octroyer les vacances en nature trouve également application de manière impérative pendant le délai de congé (<ref-ruling> consid. 2 p. 154); il n'est cependant pas absolu; en effet, une fois le contrat dénoncé, le travailleur doit chercher un autre emploi et l'employeur doit lui accorder le temps nécessaire pour le faire (<ref-law>); cette recherche étant incompatible avec la prise effective de vacances, il faut examiner dans chaque cas, au vu de l'ensemble des circonstances, telles que la durée du délai de congé, la difficulté à trouver un autre travail et le solde de jours de vacances à prendre, si l'employeur pouvait exiger que les vacances fussent prises pendant le délai de congé ou s'il doit les payer en espèces à la fin des rapports de travail (arrêt 4C.84/2002 du 22 octobre 2002 consid. 3.2.1; arrêt 4C.189/1992 du 24 novembre 1992 consid. 3b publié in SJ 1993 p. 354).
En l'espèce, la cour cantonale a soigneusement déterminé - ce qui relève des constatations de fait (<ref-law>) - le nombre de jours ouvrables disponibles entre le moment où le travail a effectivement pris fin et l'échéance de la relation contractuelle. Elle a ensuite déduit les jours ouvrables de maladie, les jours de formation continue et les jours de vacances auxquels le recourant avait droit. Elle a ainsi déterminé à 24,5 jours le temps dont le recourant avait disposé en 2010 pour rechercher un emploi. Procédant de la même façon, elle a déterminé à 9,5 jours le temps disponible pour chercher un emploi en 2011. Elle a estimé que ce laps de temps était suffisant. Savoir si le temps disponible pour chercher du travail était ou non suffisant est une question d'appréciation que le Tribunal fédéral ne peut revoir qu'avec réserve. On ne voit pas cependant que la cour cantonale ait abusé de son pouvoir d'appréciation à ce sujet.
Le recourant voudrait encore que l'on tienne compte d'un temps de préparation pour la formation continue; mais on ne saurait dire que la cour cantonale a sur ce point apprécié les faits de manière arbitraire, puisque rien ne permet d'affirmer que le recourant aurait disposé, sur ses heures de travail, de temps pour préparer sa formation continue. En tout cas, un accord des parties sur ce point n'a pas été établi.
Ainsi, la décision attaquée ne viole pas le droit fédéral.
3.
Il résulte des considérations qui précèdent que le recours doit être rejeté.
Les frais judiciaires et les dépens sont mis à la charge du recourant qui succombe (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 4'000 fr., sont mis à la charge du recourant.
3.
Le recourant versera à l'intimée une indemnité de 5'000 fr. à titre de dépens.
4.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Neuchâtel, Cour d'appel civile.
Lausanne, le 3 juin 2013
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Piaget