Faits :
A.
Par contrat de travail signé le 29 avril 1994, N._ (ci-après : l'employé) a été engagé (à partir du 1er mai 1994) par X._ PLC (ci-après : l'employeuse), société avec siège en Grande-Bretagne ayant pour but l'exploitation d'une compagnie active dans le domaine du transport aérien, en qualité de " duty engineer ", son lieu habituel de travail étant l'aéroport de Genève. En dernier lieu, son salaire mensuel net était en moyenne de 12'212 fr. (sur douze mois).
Par courrier du 28 avril 2016, l'employeuse a informé son personnel de son intention de transférer, dès le 4 juillet 2016, son service de maintenance basé à Genève à A._ AG (ci-après: la société reprenante), située dans le canton de Zurich. Tous les rapports de travail seraient automatiquement transférés (avec tous les droits et les obligations qui en découlaient), sous réserve d'un refus du transfert par un (ou des) employé (s). En cas de refus, les rapports de travail avec l'employeuse prendraient fin à l'expiration du délai de congé légal. Les employés avaient un délai au 3 juin 2016 pour s'opposer au transfert.
Il résulte de l'arrêt cantonal que, lors de précédentes restructurations (notamment en 2006), la plupart, voire la totalité des employés qui avaient été licenciés en raison d'une suppression de poste ont bénéficié d'une indemnité de départ (severance). Celle-ci concernait exclusivement les employés ayant " quitté " leur emploi et non ceux qui ne s'étaient pas opposés à leur transfert (et dont le contrat de travail avait perduré avec la société reprenante).
Par courriel du 16 mai 2016, l'employé a demandé à son employeuse de lui indiquer le montant de la prime de licenciement qu'elle avait l'intention de verser aux employés.
Le 20 mai 2016, B._, responsable des ressources humaines (RH) de l'employeuse, lui a répondu que le droit suisse n'imposait pas le versement d'une telle indemnité. Par le passé, la compagnie avait toujours tenté de trouver des accords avec les employés. Pour le cas où l'employé déciderait de refuser le transfert des rapports de travail, la société lui proposerait une indemnité équivalente à deux semaines de salaire par année de service.
L'employé a alors rétorqué que jusqu'alors, la compagnie aérienne avait toujours versé une severance de quatre semaines de salaire par année de service, que les employés aient consenti à un transfert ou non.
Par courriel du 24 mai 2016, la responsable des RH a admis que la société employeuse avait versé des indemnités de départ égales à un mois de salaire par année d'ancienneté, mais elle a exposé que des réorganisations avaient eu lieu au cours des neuf dernières années, de sorte que l'indemnité avait été réduite à deux semaines par année.
Par courriers des 28 et 29 juin 2016, l'employé s'est opposé à son transfert au sein de la société reprenante et il a réclamé le paiement d'une indemnité de départ d'un montant net de 268'664 fr., correspondant à un mois de salaire par année de service, invoquant la pratique en vigueur au sein de la compagnie et précisant qu'il n'avait jamais été informé d'un éventuel changement de pratique.
Par courrier du 1er juillet 2016, l'employeuse a contesté l'existence d'une pratique (actuelle) consistant à verser une indemnité de départ d'une telle ampleur. Elle a toutefois admis avoir versé volontairement des indemnités correspondant à deux semaines de salaire par année d'ancienneté en cas de licenciement faisant suite à une restructuration. La compagnie aérienne offrait toutefois de verser à l'employé, sur une base totalement volontaire et sans reconnaissance d'une quelconque obligation légale, une indemnité égale à deux semaines de salaire par année de service.
L'employé a refusé cette proposition.
B.
Le 25 juillet 2016, l'employé a ouvert action contre l'employeuse devant le Tribunal des prud'hommes de Genève. Après l'échec de la conciliation et la délivrance d'une autorisation de procéder, il a conclu à ce que sa partie adverse soit condamnée à lui payer la somme nette de 268'664 fr., avec intérêts moratoires à 5% l'an dès le 4 juillet 2016, à titre d'indemnité de départ.
L'employeuse a conclu à ce que le demandeur soit débouté de toutes ses conclusions.
Plusieurs témoins ont été entendus par le Tribunal, qui a renoncé à entendre douze témoins supplémentaires dont l'audition était proposée par le demandeur, au motif que la plupart d'entre eux avaient d'ores et déjà été entendus dans d'autres procédures et que la pratique de la compagnie aérienne lors des dernières restructurations ayant entraîné des licenciements avait pu être clairement établie.
Par jugement du 30 juin 2017, le Tribunal des prud'hommes a condamné la défenderesse à verser au demandeur la somme nette de 268'664 fr., intérêts en sus. En substance, il a retenu l'existence d'une pratique au sein de la compagnie aérienne selon laquelle les employés recevaient une indemnité de départ correspondant à un mois de salaire par année d'ancienneté. Elle a ensuite jugé qu'un changement de pratique (indemnité égale à deux semaines de salaire par année d'ancienneté) n'avait pas été clairement communiqué aux employés, de sorte que leur bonne foi devait être protégée et qu'ils devaient pouvoir bénéficier de la pratique initiale (= celle de 2006) qu'ils connaissaient.
Par arrêt du 5 mars 2018, la Chambre des prud'hommes de la Cour de justice du canton de Genève a admis l'appel formé par la défenderesse, annulé le jugement entrepris et, statuant à nouveau, condamné la défenderesse à verser au demandeur la somme de 134'332 fr., intérêts en sus. En substance, elle a également reconnu l'existence d'une pratique consistant à verser une indemnité de départ aux employés, mais, contrairement aux premiers juges, elle a considéré que l'employeuse avait informé les employés des nouvelles conditions applicables (deux semaines de salaire par année d'ancienneté) et que cette nouvelle pratique leur était applicable.
C.
Le demandeur exerce un recours en matière civile contre cet arrêt cantonal au Tribunal fédéral. Il conclut, principalement, à son annulation et à ce que la défenderesse soit condamnée à lui verser le montant net de 268'664 fr., intérêts en sus, subsidiairement, à son annulation et au renvoi de la cause à l'autorité précédente pour nouvelle décision. Le recourant reproche à la cour cantonale d'avoir constaté les faits de manière inexacte et d'avoir violé le droit fédéral, en particulier l'art. 9 Cst., l'art. 2 al. 2 CC, l'art. 317 CPC et les art. 18, 322 et 322d CO.
L'intimée conclut au rejet du recours.
Chacune des parties a encore déposé des observations.

Considérant en droit :
1.
Formé en temps utile (art. 100 al. 1, 45 al. 1 et 46 al. 1 let. a LTF), dirigé contre une décision finale (art. 90 LTF), rendue sur appel de la défenderesse par le tribunal supérieur du canton (art. 75 LTF) dans une affaire relevant du droit du travail (art. 72 al. 1 LTF), dont la valeur litigieuse excède 15'000 fr. (art. 74 al. 1 let. a LTF), le recours en matière civile est recevable au regard de ces dispositions.
2.
2.1. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). Il ne peut s'en écarter que si ces faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 4.1.2; <ref-ruling> consid. 5.1) - ou en violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF), et si la correction du vice est susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF).
Concernant l'appréciation des preuves, le Tribunal fédéral n'intervient, du chef de l'art. 9 Cst., que si le juge du fait n'a manifestement pas compris le sens et la portée d'un moyen de preuve, a omis sans raisons objectives de tenir compte de preuves pertinentes ou a effectué, sur la base des éléments recueillis, des déductions insoutenables (<ref-ruling> consid. 4.2; <ref-ruling> consid. 4.2; <ref-ruling> consid. 4.3; <ref-ruling> consid. 1.4.3; <ref-ruling> consid. 2.1).
La critique de l'état de fait retenu est soumise au principe strict de l'allégation énoncé par l'art. 106 al. 2 LTF (<ref-ruling> consid. 2.3 p. 266 et les références). La partie qui entend attaquer les faits constatés par l'autorité précédente doit expliquer clairement et de manière circonstanciée en quoi ces conditions seraient réalisées (<ref-ruling> consid. 1.3.1 p. 18 et les références). Si la critique ne satisfait pas à ces exigences, les allégations relatives à un état de fait qui s'écarterait de celui de la décision attaquée ne pourront pas être prises en considération (<ref-ruling> consid. 1.3.1 p. 18). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 1.3 p. 261 s.). Les faits nouveaux sont irrecevables devant le Tribunal fédéral (art. 99 al. 1 LTF).
2.2. Sous réserve de la violation des droits constitutionnels (art. 106 al. 2 LTF), le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF) à l'état de fait constaté dans l'arrêt cantonal ou, cas échéant, à l'état de fait qu'il aura rectifié. Il n'est toutefois lié ni par les motifs invoqués par les parties, ni par l'argumentation juridique retenue par l'autorité cantonale; il peut donc admettre le recours pour d'autres motifs que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 1.4 et l'arrêt cité).
3.
Vu le siège anglais de la société employeuse, la cause présente un élément d'extranéité. La question du droit applicable se résout selon la loi fédérale du 18 décembre 1987 sur le droit international privé (LDIP; RS 291), à défaut de traités internationaux (art. 1 al. 1 let. a et al. 2 LDIP). En l'espèce, les parties étaient liées par un contrat de travail, sur lequel reposent les prétentions de l'employé. En vertu de l'art. 121 al. 1 LDIP, le contrat de travail est régi par le droit de l'Etat dans lequel le travailleur accomplit habituellement son travail, soit ici le droit suisse.
4.
Selon l'autorité précédente, le droit au versement d'une indemnité de départ faisait, sur le principe, l'objet d'un accord entre les parties, ce que l'employeuse n'a pas contesté. L'employé s'en prend au montant de l'indemnité : selon lui, la cour cantonale aurait dû appliquer la pratique initiale de l'entreprise (celle de 2006) selon laquelle les employés soumis à une restructuration bénéficiaient d'un montant correspondant à un mois de salaire multiplié par le nombre d'années de service de l'employé.
Le recourant soutient que les magistrats cantonaux ont transgressé l'art. 8 CC en retenant qu'il n'avait pas démontré que l'employeuse avait continué à appliquer la pratique initiale après la restructuration de 2006. Il aurait fourni cette preuve et ce serait de manière insoutenable que les juges précédents l'ont nié : aucune autre restructuration n'ayant eu lieu entre 2006 et 2016, il lui était impossible de produire, après 2006, des exemples de versement de l'indemnité prévue initialement (un mois de salaire x nombre d'années d'ancienneté). Selon lui, il incombait à la compagnie aérienne de démontrer qu'elle avait modifié la quotité de l'indemnité et informé les employés après la restructuration de 2006, ce qu'elle n'a pas fait, la responsable des RH de l'employeuse l'ayant expressément reconnu. Il aurait ainsi droit à la quotité de l'indemnité initiale, qui faisait partie intégrante de son contrat de travail.
4.1. Il n'est en l'espèce pas nécessaire de procéder à la qualification de l'indemnité de départ ( severance) puisque, comme on va le voir, l'employé ne saurait en aucun cas prétendre à un montant supérieur à celui (134'332 fr.) qui lui a été octroyé par la cour précédente.
4.1.1. Dans l'hypothèse où cette indemnité serait qualifiée d'indemnité à raison de longs rapports de travail (art. 339b CO, titre marginal), le montant perçu par l'employé (134'332 fr.) serait quoi qu'il en soit déjà largement supérieur au montant maximal (huit mois de salaire) que le juge, en l'absence d'une clause contractuelle fixant le montant de l'indemnité, pourrait lui accorder (art. 339c al. 2 CO), ce d'autant plus qu'il conviendrait encore de déduire de ce montant les prestations versées par une institution de prévoyance (art. 339d al. 1 CO).
Certes, les parties ont la possibilité de convenir d'une dérogation en faveur de l'employé (cf. art. 339c al. 1 et 362 al. 1 CO) et, donc, de prévoir le versement d'un montant supérieur à celui fixé par la loi. En l'espèce, les parties n'ont toutefois prévu aucune dérogation, puisqu'il résulte des constatations cantonales que, indépendamment de la qualification du montant en question, elles n'ont pas eu la volonté réelle et commune de convenir d'un montant déterminé ou déterminable : le 16 mai 2016, l'employé a explicitement demandé à son employeuse de lui communiquer le montant de la prime de licenciement qu'elle avait l'intention de verser aux employés; lorsque, dans un deuxième temps, le demandeur a réclamé le versement d'une indemnité de départ d'un mois de salaire par année de service, la responsable des ressources humaines l'a d'emblée informé que la société employeuse n'avait aucune obligation de verser une telle indemnité. La démarche entreprise par l'employé le 16 mai 2016 (et, en particulier, la teneur de sa demande) n'aurait eu aucun sens si, préalablement, le montant de l'indemnité avait été déterminé par les parties (ou s'il était déterminable), ce qui indique qu'au moment de conclure leur accord, celles-ci n'avaient pas l'intention (réelle et commune) de fixer un montant déterminé (ou déterminable).
4.1.2. Dans l'hypothèse où l'indemnité de départ ( severance) - telle qu'elle a été arrêtée par l'autorité précédente - devrait être considérée comme une gratification obligatoire (le principe du versement n'étant pas contesté), il n'y aurait de toute façon pas lieu d'accorder au demandeur le montant qu'il réclame, fondé sur une pratique vieille de dix ans. L'employé n'explique en effet pas en quoi l'employeuse, qui jouirait alors d'une certaine liberté dans la fixation du montant à allouer (cf. arrêt 4A_513/2017 du 5 septembre 2018 consid. 5.3.1 et les arrêts cités), aurait abusé de cette liberté en s'écartant, en 2016, de cette ancienne pratique, alors même qu'elle a pris la peine de justifier sa décision en fonction de diverses circonstances, comme la situation économique de l'entreprise et les changements intervenus en son sein au fil des ans.
S'agissant du principe de l'égalité de traitement, auquel se réfère la cour cantonale, la question de son application dans les circonstances de l'espèce peut rester ouverte, en l'absence de recours de l'employeuse. En ce qui concerne le montant de l'indemnité, on ne voit pas en quoi la cour cantonale aurait violé le droit fédéral en se fondant sur la pratique actuelle de l'entreprise (cf. <ref-ruling> consid. 3.1 p. 281 ss). L'employé se plaint certes d'une transgression du principe de l'égalité de traitement, mais, il se limite à affirmer, de manière purement appellatoire, en citant diverses pièces du dossier cantonal, que tous les collègues placés dans la même situation que lui avaient bénéficié d'une indemnité de départ d'un mois de salaire par année de service (acte de recours p. 19 s.). La critique est dès lors irrecevable.
Le seul fait que d'anciens employés ont pu bénéficier d'indemnités de départ plus avantageuses en 2006(soit dix ans avant la restructuration de 2016) n'est à cet égard pas déterminant. On ne saurait en effet reprocher à la cour cantonale de n'avoir pas traité de manière égale le cas de l'employé avec des situations passées, alors que des changements sont intervenus dans cet intervalle et que l'indemnité accordée en 2016 tenait compte de la situation économique de l'entreprise. Les critères retenus par l'entreprise (situation économique et changements intervenus au fils des ans) ne sont pas en contradiction avec le droit fédéral et le recourant n'explique d'ailleurs pas en quoi ils le seraient.
4.1.3. Enfin, il n'y a pas lieu de déterminer si, comme le suggère le recourant, l'indemnité de départ ( severance) pourrait être considérée comme un élément de son salaire. Si le principe du versement est établi, il résulte de l'arrêt cantonal que les parties n'ont pas voulu fixer un montant déterminé (ou au moins déterminable), condition sine qua non pour qualifier une rémunération de salaire. Sur ce point, on peut reprendre mutatis mutandis les considérations déjà émises en lien avec l'art. 339b CO (cf. supra consid. 4.1.1).
Le demandeur soutient que la cour précédente a elle-même reconnu que la quotité de l'indemnité " faisait indéniablement partie tacitement du contrat " de tous les employés, de sorte que l'indemnité serait bien un élément du salaire. Son argumentation tombe à faux puisque la cour cantonale, dans le passage visé par le recourant, ne parle pas de la quotité de l'indemnité, mais qu'elle se limite à admettre qu'en vertu du principe d'égalité de traitement, " le principe du droit au versement d'une indemnité de départ est dès lors acquis ". C'est donc en vain que le recourant infère de son constat (erroné) qu'une modification de la quotité de l'indemnité ne peut être effectuée " qu'en respectant le régime de modification des éléments contractuels du rapport de travail ".
Les moyens soulevés par le recourant dans ce contexte (violation des art. 322, 322d et 18 CO) tombent dès lors à faux. De même, c'est en vain qu'il affirme, en se fondant sur la même argumentation, que l'arrêt cantonal est " manifestement insoutenable " et qu'il " heurte de manière choquante le sentiment de la justice ".
On ne saurait dès lors suivre le recourant lorsqu'il soutient que l'indemnité de départ consisterait en un élément du salaire faisant partie intégrante de son contrat de travail.
4.2. Il résulte des considérations qui précèdent que le changement de pratique entre 2006 et 2016 ne contrevient pas au principe de l'égalité de traitement (pour autant que celui-ci soit applicable en l'espèce). Cela étant, il importe peu de savoir si l'employé avait connaissance de la pratique de 2006, de sorte qu'il est inutile d'examiner si c'est en violation de l'art. 317 CPC que l'autorité précédente a établi, sur la base d'un élément de fait invoqué pour la première fois par la défenderesse dans la procédure d'appel, que le recourant n'avait pas connaissance de cette pratique ancienne.
Quant à la transgression de l'art. 2 al. 2 CC évoquée par le recourant, qui repose sur la même argumentation, elle se révèle sans consistance (acte de recours p. 19 s.).
Les critiques soulevées par le recourant sont dès lors infondées.
5.
Il résulte des considérations qui précèdent que le recours en matière civile doit être rejeté dans la mesure où il est recevable.
Les frais et 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é dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 5'000 fr, sont mis à la charge du recourant.
3.
Le recourant versera à l'intimée une indemnité de 6'000 fr. à titre de dépens.
4.
Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, Chambre des prud'hommes.
Lausanne, le 13 mars 2019
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente : Kiss
Le Greffier : Piaget