Faits :
A.
Par jugement du 7 novembre 2014, le Tribunal criminel des Montagnes et du Val-de-Ruz a condamné X._ pour infractions graves à la LStup (RS 812.121) et infractions à la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) à une peine privative de liberté de six ans, sous déduction de 394 jours de détention subie avant jugement.
B.
Par jugement du 27 mai 2015, la Cour pénale du Tribunal cantonal du canton de Neuchâtel a rejeté l'appel joint du Ministère public de la République et canton de Neuchâtel et a admis partiellement l'appel de X._ en ce sens qu'elle a réduit à cinq ans et neuf mois la peine privative de liberté.
En bref, il en ressort que X._, non-consommateur, a acquis et revendu, du 1 er septembre 2012 jusqu'à son arrestation le 10 octobre 2013, 2'699,5 grammes d'héroïne et 623,5 grammes de cocaïne. Il est en outre entré et a séjourné illégalement en Suisse entre le 1 er septembre 2012 et le 10 octobre 2013.
C.
Le Ministère public de la République et canton de Neuchâtel forme un recours en matière pénale au Tribunal fédéral contre le jugement du 27 mai 2015. Principalement, il conclut, avec suite de frais, à sa réforme en ce sens que la peine privative de liberté infligée à X._ soit augmentée à sept ans et demi. Subsidiairement, il requiert le renvoi de la cause à l'autorité précédente pour nouvelle décision.
Par ordonnance du 20 mai 2016, le Président de la Cour de droit pénal du Tribunal fédéral a admis la requête d'assistance judiciaire formée par X._.
La cour cantonale a renoncé à se déterminer et s'est référée à son jugement. X._ a conclu au rejet du recours. Ses déterminations ont été adressées à la cour cantonale et au ministère public pour information.

Considérant en droit :
1.
Le recourant se plaint d'une violation de l'<ref-law>.
1.1. L'art. 147 al. 1 1 re phrase CPP consacre le principe de l'administration des preuves en présence des parties durant la procédure d'instruction et les débats. Il en ressort que les parties ont le droit d'assister à l'administration des preuves par le ministère public et les tribunaux et de poser des questions aux comparants. Ce droit spécifique de participer et de collaborer découle du droit d'être entendu (<ref-law>). Il ne peut être restreint qu'aux conditions prévues par la loi (cf. art. 108, 146 al. 4 et 149 al. 2 let. b CPP; cf. aussi <ref-law> et Message du 21 décembre 2005 relatif à l'unification du droit de la procédure pénale, FF 2006 1166 s. ch. 2.4.1.3). Les preuves administrées en violation de l'<ref-law> ne sont pas exploitables à la charge de la partie qui n'était pas présente (<ref-law>; cf. <ref-ruling> consid. 1.2.1 p. 175; <ref-ruling> consid. 4.2 p. 29 s.).
Le droit de participer à l'administration des preuves durant l'instruction et les débats vaut en principe également pour l'audition des coprévenus (<ref-ruling> consid. 1.2.2 p. 175; <ref-ruling> consid. 5.1-5.3 p. 30 ss). Néanmoins, dans des procédures conduites séparément, la qualité de partie n'est pas accordée au prévenu dans les autres procédures concernées. Il n'existe par conséquent pas de droit de participer à l'instruction et aux débats menés séparément contre un autre prévenu (<ref-law> a contrario). La restriction du droit de participer des prévenus contre lesquels des procédures séparées sont menées en comparaison du droit de participer des coprévenus dans la même procédure a été implicitement prévue et acceptée par le législateur (<ref-ruling> consid. 1.2.3 p. 176).
Dans la mesure où les autorités de poursuite pénale se fondent sur les déclarations d'un prévenu ressortant d'une procédure conduite séparément, il faut tenir compte du droit de confrontation. Les déclarations en cause ne peuvent être utilisées que si le prévenu a eu au moins une fois durant la procédure la possibilité de manière appropriée et suffisante de mettre en doute les déclarations à sa charge et de poser des questions au prévenu contre lequel une procédure séparée est menée (cf. <ref-ruling> consid. 1.3 p. 176 et les références citées). Selon l'art. 178 let. f CPP, celui qui a le statut de prévenu dans une autre procédure doit être entendu en qualité de personne appelée à donner des renseignements. La disposition s'applique aux personnes impliquées comme coauteurs ou participants dans les faits à élucider, qui sont jugés dans une autre procédure. Le cas dans lequel non pas les mêmes infractions mais des infractions connexes sont poursuivies dans les deux procédures est également visé (<ref-ruling> consid. 1.3 p. 176; cf. FF 2006 1188 ss ch. 2.4.4).
1.2. En l'espèce, la cour cantonale a examiné si les déclarations de A._, B._ et C._ étaient exploitables. Elle a constaté que A._ avait mis en cause l'intimé à plusieurs reprises dans le cadre d'une procédure pénale parallèle, en l'absence de l'avocat de ce dernier. La police savait à ce moment-là que le premier nommé se fournissait en héroïne et en cocaïne auprès du second, de sorte que cette découverte ne pouvait être qualifiée de fortuite. Il s'agissait d'une violation des droits de la défense (auditions de A._ menées en l'absence de l'avocat de l'intimé). Sur cette base, la cour cantonale a jugé qu'elle ne pouvait se fonder que sur les déclarations faites par A._ dans des conditions régulières (soit sur les déclarations faites en présence de l'avocat de l'intimé ou de l'intimé lui-même). Le ministère public avait, autant que faire se peut, réparé ce vice en organisant une nouvelle audition de A._ en présence du mandataire de l'intimé et une confrontation. L'état de fait n'était en rien changé puisque A._ avait confirmé, lors des auditions régulières en question, l'ensemble de ses précédentes déclarations.
S'agissant de B._, il avait été entendu le 28 novembre 2013 à titre de personne appelée à donner des renseignements dans le cadre de la procédure menée contre l'intimé. Lors de cette audition, il avait mis en cause l'intimé, en présence de l'avocat de ce dernier. La police savait que B._ se fournissait auprès de l'intimé, de sorte que cette découverte ne pouvait être qualifiée de fortuite. Puisque le conseil de l'intimé avait participé à cette audition, elle était parfaitement exploitable. Le 29 novembre 2013, B._ avait été une nouvelle fois entendu, mais en qualité de prévenu. Selon la cour cantonale, le mandataire de l'intimé n'avait pas le droit d'assister à cette audition menée dans le cadre d'une procédure parallèle, puisque l'<ref-law> conférait ce droit aux parties à la procédure et non pas aux parties à une procédure parallèle. Au demeurant, B._ n'avait pas abordé la question des achats effectués auprès de l'intimé lors de cette seconde audition, mais uniquement celle de l'identité de ses propres acheteurs, de sorte que le maintien au dossier du procès-verbal de cette audition ne causait aucun préjudice au prénommé.
La cour cantonale a en outre relevé que lors des auditions de C._ effectuées par la police sur mandat de la procureure - qui sont intervenues dans le cadre d'une procédure pénale parallèle - ce dernier avait mis en cause l'intimé, en l'absence de l'avocat de celui-ci. Le 19 juin 2014, C._ avait été entendu par le ministère public, en l'absence de l'avocat de l'intimé et avait confirmé ses précédentes déclarations devant la police. Selon la cour cantonale, le droit d'être entendu de l'intimé n'avait pas été respecté. Le ministère public avait toutefois réparé cette violation des droits de la défense en réentendant C._ le 4 juillet 2014, cette fois en présence de l'avocat de l'intimé. Lors de son audition, C._ avait confirmé intégralement ses précédentes déclarations, de sorte que l'état de fait n'était en rien changé puisqu'il avait confirmé, lors des auditions régulières en question, l'ensemble de ses précédentes déclarations.
Dans le cadre de la fixation de la peine, la cour cantonale a considéré qu'il fallait tenir compte du fait que les droits de la défense de l'intimé avaient été violés et appliquer les principes développés dans sa jurisprudence (arrêt de la Cour pénale du Tribunal cantonal du canton de Neuchâtel du 23 septembre 2013 consid. 4d, in RJN 2013 p. 374). Selon l'autorité précédente, la sanction la mieux adaptée au cas d'espèce, assimilable à une violation du principe de célérité, était une réduction de la peine infligée à l'intimé. La première irrégularité constatée pour l'audition de A._ était la plus importante puisque la première audition irrégulière avait eu lieu le 10 octobre 2013 et que ce vice n'avait été réparé que le 28 mars 2014. Pour C._, elle était plus limitée car la violation avait été réparée par le ministère public à bref délai. La cour cantonale en a conclu qu'une peine réduite à cinq ans et neuf mois de privation de liberté tenait compte de l'ensemble des circonstances et facteurs déterminants et qu'elle n'était en tout cas ni exagérément sévère ni excessivement clémente.
1.3. En substance, le recourant soutient que la cour cantonale aurait, à tort, étendu le champ d'application de l'<ref-law> aux procédures distinctes conduites contre les prévenus A._ et C._. Il fait en outre valoir que l'autorité précédente aurait adopté un raisonnement contradictoire - mais néanmoins correct - au sujet de B._ et que la prétendue violation des droits de la défense de l'intimé ne devrait, en tout état, pas être sanctionnée par une application analogique de réduction de peine qui prévaut en matière de non-respect du principe de célérité.
1.4. Force est d'admettre, avec le recourant, que l'argumentation de la cour cantonale est contradictoire. En effet, on ne distingue pas la raison pour laquelle elle traite A._ et C._ différemment de B._, puisque son audition du 29 novembre 2013 a eu lieu dans le cadre d'une procédure séparée menée contre lui, à l'instar des prénommés. Conformément à la jurisprudence précitée, l'intimé ne revêtait donc pas la qualité de partie dans le cadre de ces procédures distinctes. Il n'avait ainsi pas de droit de participer à leurs auditions, ni d'ailleurs son mandataire, de sorte que l'<ref-law> ne s'applique pas en l'espèce. Pour le surplus, l'intimé ne saurait prétendre ici que le ministère public aurait commis un abus de droit en détournant les règles de procédure aux fins de le priver de ses droits de défense, puisque la cour cantonale a admis, ce qu'il ne conteste pas, la validité de la conduite de procédures séparées par dite autorité de poursuite à l'encontre de A._ et C._. Cela étant, l'intimé a été confronté à une reprise à A._. Quant à C._, outre le fait qu'il a été entendu une fois en présence du conseil de l'intimé, il ne résulte pas de la décision entreprise que ce dernier aurait expressément demandé une confrontation directe avec lui (cf. arrêt 6B_731/2009 du 9 novembre 2010 consid. 4.1, non publié in <ref-ruling>; plus récemment arrêt 6B_98/2014 du 30 septembre 2014 consid. 3.4). Partant, les droits de la défense de l'intimé ont été respectés. C'est ainsi à tort que la cour cantonale s'est fondée sur une prétendue violation desdits droits pour procéder à une réduction de peine, indépendamment de savoir si en soi une telle violation pourrait permettre une réduction de peine. La question de savoir si la quotité de la peine est conforme à l'<ref-law>, peut dès lors rester ouverte puisqu'elle doit être à nouveau fixée dans le cadre du renvoi en tenant compte de ce qui précède.
2.
Il s'ensuit que le recours doit être admis et le jugement attaqué annulé, la cause étant renvoyée à l'autorité cantonale pour qu'elle statue à nouveau sur la peine.
Le ministère public, qui obtient gain de cause, ne saurait se voir allouer de dépens (<ref-law>). L'intimé ayant obtenu l'assistance judiciaire par ordonnance du 20 mai 2016 précitée, il convient d'allouer à son mandataire le montant qu'il requiert à titre d'indemnité, qui sera supportée par la caisse du Tribunal fédéral (<ref-law>). Il est statué sans frais (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, le jugement attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Une indemnité de 1'500 fr., supportée par la Caisse du Tribunal fédéral, est allouée à Me Christian Zumsteg à titre d'honoraires.
4.
Le présent arrêt est communiqué aux parties et à la Cour pénale du Tribunal cantonal du canton de Neuchâtel.
Lausanne, le 30 juin 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Nasel