Faits:
A.
E._ travaillait comme aide de cuisine au restaurant X._. Le 17 juin 2003, il a fait une chute d'un balcon, d'une hauteur de cinq mètres environ, provoquant une fracture de type Burst de L1 ainsi que des calcanéums droit et gauche.
L'intéressé a déposé le 4 juin 2004 une demande de prestations de l'assurance-invalidité, faisant état d'atteintes au dos et aux pieds existant depuis l'accident survenu le 17 juin 2003. Dans le cadre de l'instruction de la demande et afin de clarifier les avis divergents au dossier sur la situation médicale de l'assuré, la doctoresse A._, médecin-conseil auprès du Service médical régional de l'assurance-invalidité (SMR), a préconisé la mise en oeuvre d'une expertise de type COMAI, laquelle a été confiée à la Clinique Y._. Sur le plan rhumatologique, les experts ont fait état d'un certain nombre de limitations fonctionnelles et conclu à une capacité de travail complète dans une activité assise, avec possibilité de varier les positions, sans mouvements monotones et répétitifs continus. Sur le plan psychiatrique, ils ont retenu un trouble dépressif récurrent dont l'épisode actuel était moyen sans traitement. L'état dépressif constituait une limitation à un fonctionnement professionnel normal. Compte tenu des limitations rhumatologiques, orthopédiques et psychiatriques, les experts du COMAI ont retenu une capacité de travail de l'ordre de 50 % avec une réévaluation nécessaire d'ici à deux ans, afin d'examiner une éventuelle amélioration de la capacité de travail après l'instauration d'un traitement anti-dépresseur et d'un suivi régulier spécifique sur le plan psychique (cf. rapport d'expertise du 23 mai 2008).
Le 23 juin 2008, l'assureur-accidents a transmis à l'assurance-invalidité le rapport d'enquête d'un détective qu'il avait mandaté pour effectuer des vérifications sur l'emploi du temps de l'assuré entre le 16 décembre et le 11 mars 2008. Le détective a constaté en substance que l'assuré n'avait pas de limitations fonctionnelles.
Le même jour, l'OAI a demandé au COMAI de préciser à partir de quand la capacité de travail de 50 % était exigible, si des limitations psychiatriques devaient être retenues et que soient énoncées celles ayant des répercussions sur la capacité de travail. En l'absence de la doctoresse U._ qui avait procédé à l'expertise, le docteur R._, médecin responsable de Y._, a répondu préalablement qu'il avait été conclu à une capacité exigible de l'ordre de 35 % dans une activité adaptée. Il a ensuite indiqué que si l'on se référait aux éléments du dossier, la situation était décrite comme stabilisée sur le plan orthopédique en janvier 2007 par le docteur T._ et qu'elle semblait être stabilisée après le passage institutionnel auprès du docteur F._ au début août 2007. Quant à l'évaluation de la capacité de travail, l'appréciation de 50 % tenait compte effectivement des limitations liées à l'affection psychiatrique, qui restait potentiellement améliorable par un traitement spécifique.
Dans une communication interne du Secteur de lutte contre la fraude (ci-après: LFA) de l'OAI du 3 juillet 2008, il était demandé qu'après prise de position du SMR sur le rapport du détective, notamment sur la question d'une éventuelle exagération des symptômes, voire d'une simulation, ainsi que sur l'absence de traitement anti-dépresseur, le dossier soit retourné dans ce service.
Le 25 juillet 2008, en réponse à un courrier de l'assuré lui demandant ce qu'il envisageait pour l'aider à trouver une activité adaptée à 50 %, l'OAI a répondu être dans l'attente de renseignements médicaux complémentaires demandés à la Clinique Y._ au sujet de l'expertise du 23 mai 2008.
Dans un avis médical du 5 septembre 2008, le docteur Q._, médecin au SMR, a constaté que les conditions de l'<ref-law> n'étaient pas réunies en l'espèce, cet article prévoyant que la diminution des possibilités de gain devait persister après les traitements et les mesures de réadaptation. Or, dans la mesure où l'état de santé de l'assuré pouvait s'améliorer significativement sous un traitement antidépresseur et avec un suivi de soutien, et que le traitement proposé par les experts était exigible, il convenait de demander à l'assuré de s'y soumettre et de réévaluer la situation six mois plus tard.
Par courrier du 6 octobre 2008, l'OAI a informé l'assuré qu'il envisageait, sur la base de l'expertise de Y._, de lui reconnaître le droit à une demi-rente fondée sur un degré d'invalidité de 50 % à partir du 16 juin 2004. Il enjoignait par ailleurs l'assuré à suivre le traitement médical nécessaire (prise d'un anti-dépresseur ainsi que suivi de soutien par le médecin traitant ou un médecin psychiatre), précisant qu'un contrôle par des tests adaptés (dosages plasmatiques) serait fait régulièrement et les résultats transmis à l'assurance.
Le 11 novembre 2008, l'OAI a notifié à l'assuré un projet d'acceptation de rente par lequel il lui reconnaissait le droit à une demi-rente d'invalidité avec effet au 1 er juin 2004.
Dans une " fiche d'examen du dossier " du 16 février 2009, l'OAI a mentionné une lettre de l'assureur-accidents du 7 janvier 2009 qui contestait le projet d'acceptation de rente et prévoyait de compléter son dossier par une expertise. L'OAI s'est en outre demandé, dans la mesure où il s'agissait d'un cas LFA, s'il ne fallait pas attendre les résultats avant de rendre sa décision. Enfin, l'OAI a indiqué que par lettre du 13 février 2009, il avait demandé à la caisse de compensation de suspendre le calcul de la rente.
L'assureur-accidents a soumis l'assuré à une nouvelle expertise qu'il a confiée aux docteurs C._ (spécialiste FMH en psychiatrie et psychothérapie) et M._ (spécialiste FMH en chirurgie orthopédique). Dans son rapport du 16 novembre 2009, le docteur M._ a posé le diagnostic de lombalgies chroniques sur status après fracture Burst de L1 et podalgies bilatérales sur status après fracture complexe des deux calcanéums avec arthrose sous-astragalienne. La capacité de travail de l'assuré était nulle dans son ancienne profession d'aide de cuisine. Toutefois, dans une activité adaptée, en position alternée assis-debout, sans port de charges au-delà de 10 kg et sans travaux lourds et/ou pénibles, une capacité de travail entière était exigible. Dans son rapport d'expertise du 29 décembre 2009, l'expert-psychiatre a posé le diagnostic d'abus d'alcool, de trouble dépressif récurrent (état actuel léger) et de trouble mixte de la personnalité. Il a conclu à une incapacité de travail psychiatrique de 60 % entre le 16 juin 2003 et le 30 juin 2004. A partir du 1 er juillet 2004, l'assuré avait récupéré une pleine capacité de travail sur le plan psychiatrique, quelle que soit l'activité proposée. Par avis médical du 15 mars 2010, le docteur Q._, du SMR, s'est rallié aux conclusions des experts précités.
Le 17 juin 2010, l'OAI a notifié à l'assuré un projet d'acceptation de rente annulant et remplaçant celui du 11 novembre 2008, par lequel il lui octroyait le droit à un trois-quarts de rente d'invalidité du 16 juin au 30 septembre 2004, aucune prestation n'étant allouée au-delà de cette date. Par décision du 16 mai 2011, l'OAI a alloué à l'assuré un trois-quarts de rente d'invalidité du 1 er juin au 30 septembre 2004.
B.
E._ a recouru contre cette décision devant la Cour des assurances sociales du Tribunal cantonal, en concluant à l'octroi d'une demi-rente dès le 1 er juin 2004.
Par jugement du 25 juin 2012, la juridiction cantonale a rejeté le recours.
C.
E._ interjette un recours en matière de droit public contre ce jugement dont il demande la réforme en concluant derechef à l'octroi d'une demi-rente d'invalidité dès le 1 er juin 2004. A l'appui de son recours, il a demandé le bénéfice de l'assistance judiciaire gratuite.
L'OAI a conclu implicitement au rejet du recours tandis que l'Office fédéral des assurances sociales ne s'est pas déterminé.

Considérant en droit:
1.
Le recours en matière de droit public (<ref-law>) peut être formé pour violation du droit selon l'art. 95 sv. LTF. Le Tribunal fédéral applique le droit d'office (<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 (cf. <ref-ruling> consid. 1.4 p. 140). Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>) et peut rectifier ou compléter d'office les constatations de celle-ci si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>).
2.
Le litige porte sur le droit du recourant à une rente d'invalidité au-delà du 30 septembre 2004, singulièrement sur le point de savoir si l'OAI pouvait se fonder sur les expertises des docteurs C._ et M._ pour nier le droit aux prestations de l'assurance-invalidité au-delà de cette date. Il s'agit d'examiner si, comme le soutient le recourant, l'instruction du cas était complète lorsque Y._ a rendu son rapport d'expertise ou s'il pouvait encore être tenu compte des expertises des docteurs C._ et M._ pour apprécier la capacité de travail du recourant et, partant, son droit éventuel à une rente.
3.
Le recourant soutient qu'en discutant du point de savoir laquelle des expertises de Y._ d'une part, et celles des docteurs C._ et M._ d'autre part, était la plus probante, les premiers juges ont violé le droit. La question qui se posait en l'espèce était plutôt celle de savoir si l'OAI "pouvait dire que l'expertise de Y._ du 23 mai 2008 était si peu probante qu'il fallait en mettre en oeuvre une deuxième". Or, selon le recourant, l'OAI n'avait jamais prétendu au défaut de valeur probante de l'expertise de Y._ et les premiers juges n'en avaient pas fait la démonstration. Se prévalant en outre du principe de protection de la bonne foi, le recourant fait valoir que l'OAI "aurait, s'il n'avait pas voulu se contredire et tromper, dû, sans attendre, donner à son projet de décision du 11 novembre 2008 la forme d'une décision".
4.
4.1. Dans le domaine des assurances sociales notamment, la procédure est régie par le principe inquisitoire, selon lequel les faits pertinents de la cause doivent être constatés d'office par l'assureur, qui prend les mesures d'instruction nécessaires et recueille les renseignements dont il a besoin (cf. <ref-law>). Le devoir d'instruction s'étend jusqu'à ce que les faits nécessaires à l'examen des prétentions en cause soient suffisamment élucidés (arrêt 8C_364/2007 du 19 novembre 2007 consid. 3.2). Dans la conduite de la procédure, l'assureur dispose d'un large pouvoir d'appréciation en ce qui concerne la nécessité, l'étendue et l'adéquation de recueillir des données médicales.
De son côté, conformément à son devoir de collaborer à l'instruction de l'affaire (<ref-ruling> consid. 2 p. 195), l'assuré est tenu de se soumettre aux examens médicaux et techniques qui sont nécessaires à l'appréciation du cas et peuvent être raisonnablement exigés (<ref-law>). En ce sens (arrêt U 571/06 du 29 mai 2007 consid. 4.1, in RSAS 2008 p. 181), le pouvoir d'appréciation de l'administration dans la mise en oeuvre d'un examen médical n'est pas illimité; elle doit se laisser guider par les principes de l'Etat de droit, tels les devoirs d'objectivité et d'impartialité (cf. ULRICH MEYER-BLASER, Das medizinische Gutachten aus sozialrechtlicher Sicht, in ADRIAN M. SIEGEL/DANIEL FISCHER, Die neurologische Begutachtung, Schweizerisches medico-legales Handbuch, vol. 1, 2004, p. 105) et le principe d'une administration rationnelle (cf. MARKUS FUCHS, Rechtsfragen im Rahmen des Abklärungsverfahrens bei Unfällen, in RSAS 2006 p. 288).
4.2. Selon la jurisprudence (arrêt 9C_1012/2008 du 30 juin 2009 consid. 3.2.2 et la référence citée), le devoir de prendre d'office les mesures d'instruction nécessaires à l'appréciation du cas au sens de l'<ref-law> ne comprend pas le droit de l'assureur de recueillir une "second opinion" sur les faits déjà établis par une expertise, lorsque celle-ci ne lui convient pas. L'assuré ne dispose pas non plus d'une telle possibilité. Il ne s'agit en particulier pas de remettre en question l'opportunité d'une évaluation médicale au moyen d'un second avis médical, mais de voir dans quelles mesure et étendue une instruction sur le plan médical doit être ordonnée pour que l'état de fait déterminant du point de vue juridique puisse être considéré comme établi au degré de la vraisemblance prépondérante (Kieser, ATSG-Kommentar, 2 e éd., n. 12 et 17 ad <ref-law>). La nécessité de mettre en oeuvre une nouvelle expertise découle du point de savoir si les rapports médicaux au dossier remplissent les exigences matérielles et formelles auxquelles sont soumises les expertises médicales. Cela dépend de manière décisive de la question de savoir si le rapport médical traite de façon complète et circonstanciée des points litigieux, se fonde sur des examens complets, prend également en considération les plaintes exprimées par la personne examinée, a été établi en pleine connaissance de l'anamnèse et contient une description du contexte médical et une appréciation de la situation médicale claires, ainsi que des conclusions dûment motivées de l'expert (<ref-ruling> consid. 3a p. 352).
5.
5.1. Contrairement à ce que soutient le recourant, la juridiction cantonale ne s'est pas contentée de comparer l'expertise de Y._ avec celles des experts C._ et M._. Ce n'est en effet qu'après être arrivée à la conclusion que le projet d'acceptation de rente du 11 novembre 2008 avait été rendu avant que l'instruction du dossier ne fût terminée que les premiers juges ont procédé à une appréciation des preuves en tenant compte des expertises des docteurs C._ et M._.
5.2. Des faits constatés par la juridiction cantonale, il ressort qu'à la lecture du rapport d'expertise de Y._, la doctoresse A._ avait constaté des imprécisions au sujet de la capacité de travail exigible dans une activité adaptée et avait requis des experts des informations complémentaires. Les réponses n'avaient toutefois pas été apportées par les spécialistes ayant rédigé le rapport ou procédé aux expertises mais par un tiers, le docteur R._, et étaient restées imprécises. Par ailleurs, le secteur LFA entendait examiner le cas après avis du SMR sur la question d'une éventuelle exagération des symptômes, voire d'une simulation, et sur l'absence de traitement anti-dépresseur et de suivi thérapeutique. L'OAI avait à cet effet informé le recourant qu'il requérait des renseignements médicaux complémentaires à la Clinique Y._ au sujet de l'expertise du 23 mai 2008. Le docteur Q._, du SMR, avait ensuite préconisé de demander à l'assuré de se soumettre à un traitement antidépresseur avec un suivi de soutien, dans la mesure où l'expert de Y._ mentionnait que son état de santé pouvait s'améliorer significativement sous ce traitement et de réévaluer la situation dans les six mois. Sur cette base, l'OAI avait adressé un courrier au recourant lui expliquant qu'il envisageait de lui reconnaître le droit à une demi-rentre d'invalidité dès le 16 juin 2004. Toutefois, il l'enjoignait à suivre le traitement médical, précisant qu'un contrôle serait fait régulièrement.
5.3. La manière de procéder de l'intimé apparaît conforme au droit. Dans un premier temps, l'OAI a requis des précisions de la part des experts du COMAI, leur appréciation n'ayant pas été jugée suffisamment concluante. Les clarifications apportées par le docteur R._ sont restées imprécises, voire contradictoires. Par ailleurs, le secteur LFA avait fait part de ses doutes quant à une éventuelle exagération des symptômes. Il avait en outre été demandé expressément à l'assuré de suivre le traitement nécessaire à l'amélioration de son état de santé auprès de son médecin traitant ou d'un psychiatre. Par ailleurs, l'assureur-accidents avait contesté le projet d'acceptation de rente et prévoyait de compléter son dossier par une expertise. Dès lors que l'examen médical ordonné par l'assureur-accident n'avait pas seulement pour but de déterminer le lien de causalité entre l'atteinte psychiatrique et l'accident mais également les incapacité de travail liées à chacune des atteintes (somatique et psychiatrique) et l'évolution de celles-ci, on ne saurait reprocher à l'intimé d'avoir voulu recueillir une "second opinion" à l'encontre de l'expertise du COMAI qui ne lui aurait pas convenu. Un tel reproche aurait tout au plus pu être formulé si l'intimé avait écarté cette expertise sans aucun motif, avant d'en ordonner immédiatement une nouvelle sur les mêmes points à examiner (cf. aussi arrêt 9C_1012/2008 du 30 juin 2009 précité, consid. 3.4).
5.4. Se fondant sur l'art. 5 Cst., le recourant fait en outre valoir qu'en ne donnant pas à son projet de décision du 11 novembre 2008 la forme d'une décision, l'OAI a adopté un comportement contradictoire et trompeur.
Aux termes de l'art. 5 al. 3 Cst., les organes de l'Etat et les particuliers doivent agir conformément aux règles de la bonne foi. Cela implique notamment qu'ils s'abstiennent d'adopter un comportement contradictoire ou abusif (<ref-ruling> consid. 4.2 p. 312). De ce principe découle notamment, en vertu de l'art. 9 Cst., le droit de toute personne à la protection de sa bonne foi dans ses relations avec l'Etat (sur le rapport avec l'art. 5 al. 3 Cst., cf. <ref-ruling> consid. 5.2 p. 261 et la référence citée). Le principe de la bonne foi protège le citoyen dans la confiance légitime qu'il met dans les assurances reçues des autorités, lorsqu'il a réglé sa conduite d'après des décisions, des déclarations ou un comportement déterminé de l'administration (cf. <ref-ruling> consid. 6.1 p. 636).
Indépendamment de la portée du projet d'acceptation de rente du 11 novembre 2008 sous l'angle de la protection de la bonne foi, il y a lieu de constater que le recourant n'a pas établi ni même prétendu avoir pris des dispositions contraires à ses intérêts et sur lesquelles il ne pouvait plus revenir. Pour cette raison déjà, le moyen soulevé ici est mal fondé.
5.5. Il résulte de ce qui précède qu'à l'instar de l'OAI, les premiers juges pouvaient tenir compte des expertises mises en oeuvre par l'assureur-accidents pour évaluer la capacité de travail résiduelle du recourant.
6.
La juridiction cantonale a considéré, en se fondant sur les conclusions des experts C._ et M._, que la capacité de travail du recourant était entière dans toute activité adaptée à ses limitations fonctionnelles dès le 1er juillet 2004 et ce, tant sur les plans somatique que psychique. Dans la mesure où la capacité de travail avait toutefois été réduite de 60 % pendant la période du 16 juin 2003 au 30 juin 2004, la juridiction cantonale a confirmé le droit à un trois-quarts de rente d'invalidité pour la période du 1er juin au 30 septembre 2004. Le recourant ne formule aucun grief à l'encontre des expertises des docteurs C._ et M._, de sorte qu'il n'y a pas lieu de remettre en cause le bien-fondé des expertises réalisées par lesdits experts et, partant, le résultat de l'appréciation des preuves opérée par la juridiction cantonale.
7.
Vu l'issue du litige, les frais judiciaires doivent être mis à la charge du recourant qui succombe (<ref-law>). Il remplit toutefois les conditions du droit à l'assistance judiciaire dont il a requis le bénéfice (<ref-law>), dès lors que le recours n'était pas d'emblée voué à l'échec, qu'il ne dispose pas de ressources suffisantes et que l'assistance d'un avocat était indiquée. Le recourant sera ainsi provisoirement dispensé de payer les frais de justice et les honoraires de son mandataire d'office seront pris en charge par la caisse du Tribunal; le recourant est toutefois rendu attentif au fait qu'il devra rembourser la caisse du Tribunal, s'il retrouve ultérieurement une situation financière lui permettant de le faire.

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
L'assistance judiciaire est accordée et Maître Jean-Marie Agier est désigné comme avocat d'office du recourant.
3.
Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant. Ils sont toutefois supportés provisoirement par la caisse du Tribunal.
4.
Une indemnité de 2'000 fr. est allouée à l'avocat du recourant à titre d'honoraires à payer par la caisse du Tribunal.
5.
Le présent arrêt est communiqué aux parties, à la Caisse de pensions Gastrosuisse, au Tribunal cantonal du canton de Vaud, Cour des assurances sociales, et à l'Office fédéral des assurances sociales.
Lucerne, le 12 juin 2013
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
La Présidente: Leuzinger
La Greffière: Fretz Perrin