Faits: A. A.a. X._ est un footballeur professionnel guinéen, né le 2 janvier 1985. Depuis 2005, il a régulièrement fait partie de l'équipe nationale de Guinée et en est devenu l'un des joueurs les plus en vue. Z._ est un club de football professionnel, membre de la Fédération de football des Emirats Arabes Unis (ci-après: UAEFA), elle-même affiliée à la Fédération Internationale de Football Association (FIFA). A._ est un club de football professionnel français, membre de la Fédération Française de Football (FFF), laquelle est affiliée à l'Union des Associations Européennes de Football (UEFA) ainsi qu'à la FIFA. A l'époque des événements qui seront relatés ci-après, il disputait le championnat de Ligue 2 (deuxième division). Depuis lors, il a été promu en Ligue 1 (première division). A.b. Le 2 septembre 2010, X._, transféré du Stade B._, club français de Ligue 1, a conclu avec Z._ un contrat de travail valable jusqu'au 30 juin 2014. Les parties sont convenues que le footballeur aurait droit, la première année, à une rémunération totale de 1'200'000 euros comprenant une avance de 240'000 euros, le solde devant être payé par tranches la première semaine de chaque mois. Ces modalités valaient également pour la deuxième année, mais l'avance était portée à 360'000 euros. Le 24 octobre 2011, Z._ a désenregistré (rem.: par souci de clarté, ce néologisme et celui de désenregistrement seront utilisés dans la suite du texte du présent arrêt) X._ de la liste des footballeurs étrangers autorisés à jouer pour le club. En date du 31 janvier 2012, X._, qui avait quitté définitivement ... sans l'autorisation de Z._ le 20 décembre 2011, a signé un contrat de travail avec A._. L'UAEFA a refusé de transmettre le Certificat International de Transfert (CIT) à la FFF au motif que le joueur guinéen était toujours sous contrat avec Z._. Cependant, par décision du 9 février 2012, le juge unique de la Commission du Statut du Joueur de la FIFA a autorisé la FFF à enregistrer provisoirement X._ en tant que joueur de A._. A.c. Le 3 janvier 2012, X._ avait assigné Z._ devant la Chambre de Résolution des Litiges de la FIFA (CRL) en vue d'obtenir le paiement de 3'400'000 euros. Il reprochait au club des Emirats Arabes Unis d'avoir rompu le contrat de travail en le désenregistrant de son effectif et, au surplus, de ne pas lui avoir versé un acompte de 180'000 fr. qui lui était dû. Dans sa réponse du 27 avril 2012, Z._ a contesté le bien-fondé de ces reproches. Il a conclu, de son côté, à ce que le joueur et A._ fussent condamnés solidairement à lui payer un montant de 9'700'000 euros, plus intérêts, pour rupture injustifiée du contrat. Dans une réponse commune du 2 août 2012, les défendeurs reconventionnels se sont opposés à l'admission de cette conclusion. A._ a nié, en tout état de cause, avoir incité le joueur à rompre son contrat de travail. Par décision du 16 novembre 2012, la CRL a admis partiellement la demande principale et condamné Z._ à payer le montant de 180'000 euros à X._. Admettant aussi une partie de la demande reconventionnelle, elle a condamné solidairement le joueur et A._ à payer à Z._ la somme de 4'500'000 euros, avec intérêts à 5% l'an dès le 16 novembre 2012. Elle a, de plus, exclu X._ de toute participation à des matchs officiels pour une durée de quatre mois, dont à déduire trois mois de suspension déjà purgés. Enfin, elle a interdit à A._ d'enregistrer de nouveaux joueurs, au niveau national et international, au cours des deux périodes consécutives d'enregistrement suivant la notification de sa décision. B. Le 21 février 2013, A._ a saisi le Tribunal Arbitral du Sport (TAS) d'un appel dirigé contre la décision de la CRL (cause CAS/2013/A/3091). X._ et Z._ en ont fait de même le lendemain (causes CAS/2013/A/3092, resp. CAS/2013/A/3093). Les causes ont été jointes. Une Formation de trois membres a été constituée pour les traiter. La FIFA a participé à la procédure arbitrale. Par sentence du 3 juin 2013, le TAS a rejeté les trois appels et confirmé la décision attaquée. En résumé, les arbitres ont examiné, à la lumière du Règlement du Statut et du Transfert des Joueurs édicté par la FIFA en 2010 (RSTJ), si la rupture du contrat par X._ était intervenue pour juste cause (art. 14 RSTJ). A cet égard, ils ont considéré que le défaut de paiement, en temps voulu, d'une moitié de l'acompte de 360'000 euros stipulé dans le contrat de travail n'en constituait pas une, s'agissant d'un manquement ponctuel de Z._ à l'une de ses obligations et faute d'un avertissement préalable du joueur avant la rupture abrupte des relations contractuelles. Il en allait de même des doléances de X._ quant au paiement de son salaire. La Formation a laissé ouverte la question de savoir si la première année de travail avait pris fin en juin 2011 (thèse du joueur) ou en août 2011 (thèse de Z._). Elle a, en effet, admis que le salaire de 1'200'000 euros, auquel le joueur avait droit pour la saison 2010/2011, avait été intégralement payé par le versement de mensualités de 80'000 euros sur une période d'une année, en sus de l'acompte de 240'000 euros. L'intéressé n'avait d'ailleurs pas contesté, à l'époque, ces modalités de paiement de sa rémunération. En ce qui concerne le désenregistrement du joueur, les arbitres ont certes reconnu que pareille démarche pouvait constituer en soi une juste cause de rupture du contrat. Toutefois, selon eux, le footballeur, étant donné les circonstances, ne pouvait pas se prévaloir de son désenregistrement comme juste cause, au sens de l'art. 14 RSTJ, pour se délier unilatéralement et sans délai de ses obligations envers le club avec lequel il était toujours sous contrat. Dès lors, X._ était tenu de verser à Z._ une indemnité à calculer selon les critères indiqués à l'art. 17 al. 1 RSTJ et A._ était solidairement responsable du paiement de cette indemnité (art. 17 al. 2 RSTJ). Aux yeux des arbitres, la manière dont l'indemnité, arrêtée à 4'500'000 euros par la CRL, avait été fixée ne prêtait pas le flanc à la critique sur le vu des arguments avancés de part et d'autre à son sujet. La décision attaquée devait donc être confirmée sur ce point. Les sanctions sportives infligées au joueur guinéen et à A._ devaient l'être également sur la base de l'art. 17 al. 3 et 4 RSTJ. Le club français n'avait du reste pas réussi à renverser la présomption, posée à l'art. 17 al. 4 RSTJ, voulant qu'un club qui signe un contrat avec un joueur professionnel ayant rompu son ancien contrat sans juste cause est censé, jusqu'à preuve du contraire, avoir incité ce joueur professionnel à une rupture de contrat. C. Le 10 juin 2013, A._ (ci-après: le recourant) a formé un recours en matière civile au Tribunal fédéral, assorti d'une requête urgente d'effet suspensif, à l'encontre de la sentence du TAS dont seul le dispositif avait été communiqué aux parties. La requête d'effet suspensif a été admise à titre superprovisionnel par ordonnance présidentielle du 13 juin 2013. En date du 3 septembre 2013, le recourant a déposé un mémoire complémentaire après avoir reçu les motifs de la sentence qui avaient été notifiés aux parties le 3 juillet 2013. Il y fait valoir, outre une violation du droit d'être entendu (art. 190 al. 2 let. d LDIP), une incompatibilité de la sentence attaquée avec l'ordre public (art. 190 al. 2 let. e LDIP) du fait que celle-ci porterait atteinte, selon lui, à la liberté économique et aux droits de la personnalité du joueur, aux règles sur le fardeau de la preuve ainsi qu'à l'interdiction des engagements excessifs. Dans sa réponse du 28 octobre 2013, la FIFA (ci-après: l'intimée) a conclu au rejet du recours pour autant qu'il fût recevable. Z._ (ci-après: l'intimé) en a fait de même dans sa réponse du 20 novembre 2013. Quant au TAS, il a proposé le rejet du recours à la fin de sa réponse du 7 novembre 2013. Pour sa part, X._ (ci-après: le joueur ou le footballeur) n'a pas déposé de réponse dans le délai qui lui avait été imparti pour ce faire. Le recourant a encore déposé de brèves observations dans une lettre du 6 décembre 2013 sur laquelle l'intimée s'est déterminée par courrier du 10 janvier 2014. D. Le 25 septembre 2013, le footballeur a, lui aussi, formé un recours en matière civile au Tribunal fédéral (cause 4A_476/2013). Son recours a toutefois été déclaré irrecevable, par arrêt du 6 janvier 2014, pour avoir été déposé hors délai. 