Faits:
A.
A._ a été engagé dès le 13 septembre 1999 en qualité de maçon par l'entreprise X._ SA. Le 2 avril 2009, il a glissé et chuté sur son côté gauche en enjambant un muret sur un chantier alors qu'il portait de lourds outils. Bien qu'il ait ressenti des douleurs dans la région axillaire, l'épaule et le bras gauches et rencontré des difficultés à effectuer certains mouvements, il a continué à travailler jusqu'au 30 avril 2009 avant de consulter un médecin. Dès cette date, il a cessé d'exercer toute activité lucrative. La Caisse nationale suisse d'assurance en cas d'accidents (CNA) a pris en charge le cas.
Se fondant notamment sur le résultat d'une arthro-IRM de l'épaule gauche effectuée le 18 juin 2009, le docteur C._, spécialiste FMH en médecine interne, a posé le diagnostic de rupture du tendon du sus-épineux, d'atteinte partielle du sous-scapulaire et dans une moindre mesure du sous-épineux (rapport du 3 juillet 2009).
Le 15 décembre 2009, A._ a déposé une demande de prestations auprès de l'Office de l'assurance-invalidité du canton de Neuchâtel (ci-près: l'OAI).
Dans le cadre de l'instruction de la demande, l'OAI a confié la réalisation d'une expertise au docteur U._, spécialiste FMH en rhumatologie et en médecine interne. Ce praticien a retenu comme diagnostics avec répercussion sur la capacité de travail, des omalgies bilatérales chroniques, un syndrome lombo-vertébral récurrent sans signe radiculaire irritatif ou déficitaire (discopathie L4-L5 sans conflit radiculaire), un syndrome cervico-brachial récurrent sans signe radiculaire irritatif ou déficitaire (discopathie multi-étagée modérée) et un syndrome polyinsertionnel douloureux récurrent (diminution du seuil de tolérance à la douleur). Il a conclu à une capacité de travail de 80 % dans une activité adaptée, c'est-à-dire respectant les limitations fonctionnelles suivantes: les mouvements en porte-à-faux répétitifs de manière prolongée, le port de charges de plus de 10 kilos ainsi que les mouvements des membres supérieurs au-dessus de l'horizontale (cf. rapport d'expertise du 18 octobre 2010 et correctifs et complément des 10 mars et 5 juillet 2011).
Par décision du 15 février 2011, confirmée sur opposition le 26 août 2011, la CNA a alloué à A._, dès le 1 er novembre 2010, une rente d'invalidité de 25 %, ainsi qu'une indemnité pour atteinte à l'intégrité fondée sur un taux de 19 %.
Se fondant sur les conclusions de l'expert U._, l'OAI a octroyé à l'assuré une demi-rente d'invalidité dès le 1 er juin 2010 (cf. décision du 13 octobre 2011).
B.
Saisie d'un recours contre la décision de l'OAI, la Cour de droit public du Tribunal cantonal neuchâtelois l'a rejeté par jugement du 17 janvier 2013.
Par jugement du même jour, cette même Cour a partiellement admis le recours contre la décision sur opposition de la CNA du 26 août 2011. Elle l'a annulée en tant qu'elle constatait que l'indemnité pour atteinte à l'intégrité n'était pas contestée et renvoyé la cause à la CNA pour instruction complémentaire et nouvelle décision sur ce point. Elle a rejeté le recours pour le surplus.
C.
A._ interjette un recours en matière de droit public contre le jugement du 17 janvier 2013 en matière d'assurance-invalidité, en concluant à l'octroi d'une rente entière d'invalidité dès le 1 er juin 2010.
Tant l'OAI que l'Office fédéral des assurances sociales ont renoncé à se déterminer.
D.
Par arrêt de ce jour, le Tribunal fédéral a rejeté le recours de l'assuré contre le jugement cantonal du 17 janvier 2013 en matière d'assurance-accidents (8C_149/2013).

Considérant en droit:
1.
Saisi d'un recours en matière de droit public (<ref-law>), le Tribunal fédéral exerce un pouvoir d'examen limité. Il applique le droit d'office (<ref-law>) et statue en principe sur la base des faits retenus par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. Le recourant ne peut critiquer la constatation de faits importants pour le jugement en cause que si ceux-ci ont été établis en violation du droit au sens de l'<ref-law> ou de manière manifestement inexacte (<ref-law>), c'est-à-dire insoutenable, voire arbitraire, et si la correction du vice est susceptible d'influer sur le sort de la cause.
2.
A l'instar de l'OAI, la juridiction cantonale a suivi les conclusions de l'expertise du docteur U._. Elle a ainsi retenu que l'état de santé de A._ était compatible avec l'exercice d'une activité adaptée à 80 %. Pour fixer son taux d'invalidité, les premiers juges ont retenu un revenu sans invalidité de 77'480 fr. et un revenu d'invalide de 37'515 fr. Pour calculer ce dernier, ils se sont référés aux données salariales statistiques ressortant de l'Enquête suisse sur la structure des salaires [ESS] valables en 2008, singulièrement au salaire obtenu par les hommes exerçant une activité simple et répétitive (niveau de qualification 4) dans le secteur privé pour un horaire hebdomadaire de travail de 41,6 heures, indexé jusqu'en 2010 (année déterminante pour le droit à la rente). Ils ont encore réduit ce salaire de 25 % pour tenir compte des limitations fonctionnelles et du manque de formation de l'assuré. Il en résultait un degré d'invalidité de 52 %, lequel ouvrait droit à une demi-rente d'invalidité.
3.
3.1. Le recourant conteste le revenu d'invalide pris en considération pour évaluer son taux d'invalidité. Il estime qu'au vu de ses importantes limitations fonctionnelles, de son âge, son manque de formation ainsi que ses difficultés linguistiques, on ne saurait raisonnablement exiger de lui qu'il reprenne un quelconque emploi.
3.2. Lorsqu'il s'agit d'examiner dans quelle mesure un assuré peut encore exploiter économiquement sa capacité de gain résiduelle sur le marché du travail entrant en considération pour lui (<ref-law>), on ne saurait subordonner la concrétisation des possibilités de travail et des perspectives de gain à des exigences excessives; l'examen des faits doit être mené de manière à garantir dans un cas particulier que le degré d'invalidité est établi avec certitude. Il s'ensuit que pour évaluer l'invalidité, il n'y a pas lieu d'examiner la question de savoir si un invalide peut être placé eu égard aux conditions concrètes du marché du travail, mais uniquement de se demander s'il pourrait encore exploiter économiquement sa capacité résiduelle de travail lorsque les places de travail disponibles correspondent à l'offre de la main d'oeuvre (arrêt I 198/97 du 7 juillet 1998 consid. 3b et les références, in VSI 1998 p. 293). On ne saurait toutefois se fonder sur des possibilités de travail irréalistes. Ainsi, on ne peut parler d'une activité exigible au sens de l'<ref-law>, lorsqu'elle ne peut être exercée que sous une forme tellement restreinte qu'elle n'existe pratiquement pas sur le marché général du travail ou que son exercice suppose de la part de l'employeur des concessions irréalistes et que, de ce fait, il semble exclu de trouver un emploi correspondant (arrêts I 350/89 du 30 avril 1991 consid. 3b, in RCC 1991 p. 329; I 329/88 du 25 janvier 1989 consid. 4a, in RCC 1989 p. 328). S'il est vrai que des facteurs tels que l'âge, le manque de formation ou les difficultés linguistiques jouent un rôle non négligeable pour déterminer dans un cas concret les activités que l'on peut encore raisonnablement exiger d'un assuré, ils ne constituent pas, en règle générale, des circonstances supplémentaires qui, à part le caractère raisonnablement exigible d'une activité, sont susceptibles d'influencer l'étendue de l'invalidité, même s'ils rendent parfois difficile, voire impossible la recherche d'une place et, partant, l'utilisation de la capacité de travail résiduelle (arrêt I 377/98 du 28 juillet 1999 consid. 1 et les références, in VSI 1999 p. 246). Toutefois, lorsqu'il s'agit d'évaluer l'invalidité d'un assuré qui se trouve proche de l'âge donnant droit à la rente de vieillesse, il faut procéder à une analyse globale de la situation et se demander si, de manière réaliste, cet assuré est en mesure de retrouver un emploi sur un marché équilibré du travail. Cela revient à déterminer, dans le cas concret qui est soumis à l'administration ou au juge, si un employeur potentiel consentirait objectivement à engager l'assuré, compte tenu notamment des activités qui restent exigibles de sa part en raison d'affections physiques ou psychiques, de l'adaptation éventuelle de son poste de travail à son handicap, de son expérience professionnelle et de sa situation sociale, de ses capacités d'adaptation à un nouvel emploi, du salaire et des contributions patronales à la prévoyance professionnelle obligatoire, ainsi que de la durée prévisible des rapports de travail (cf. arrêt I 819/04 du 27 mai 2005 consid. 2.2 et les références).
3.3. Dans le cas particulier, le tribunal cantonal a appliqué de manière correcte la jurisprudence du Tribunal fédéral et, partant, n'a pas violé le droit fédéral. Compte tenu du contexte personnel et professionnel, la mise en valeur par le recourant d'une capacité de travail de 80 % dans une activité adaptée à son état de santé est en effet objectivement exigible. Agé de 57 ans au moment de la naissance du droit à la rente, il n'avait pas encore atteint l'âge à partir duquel la jurisprudence considère généralement qu'il n'existe plus de possibilité réaliste de mise en valeur de la capacité résiduelle de travail sur un marché du travail supposé équilibré. Au demeurant, il convient d'admettre que ledit marché du travail offre un éventail suffisamment large d'activités légères, dont un nombre significatif sont adaptées aux limitations fonctionnelles du recourant et accessibles sans aucune formation particulière. En procédant par ailleurs à l'abattement maximal de 25 % (<ref-ruling> consid. 5.2 p. 328), l'OAI a suffisamment tenu compte des limitations liées au handicap et à l'absence de formation professionnelle. Quant aux difficultés linguistiques alléguées, on relèvera que le docteur U._ a fait état, comme facteurs de bon pronostic, d'une maîtrise du français et d'une bonne intelligence du recourant (cf. expertise du 18 octobre 2010, p. 13).
4.
Mal fondé, le recours doit être rejeté. Le recourant, qui succombe, supportera les frais judiciaires afférents à la présente procédure (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties, au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, et à l'Office fédéral des assurances sociales.
Lucerne, le 23 septembre 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