Sachverhalt:
A.
Der 1954 geborene A._ ist ausgebildeter Koch und Konditor. Er war zuletzt ab März 2010 als Sous-Chef Küche im Hotel B._ tätig. Am 10. Mai 2013 kündigte die Arbeitgeberin das Anstellungsverhältnis aus wirtschaftlichen Gründen auf den 31. Juli 2013. Im November 2013 meldete sich A._ unter Hinweis auf einen Zustand nach operativ behandeltem Aortariss und notfallmässiger Operation am rechten Bein mit seither bestehenden Fussbeschwerden zum Leistungsbezug bei der Invalidenversicherung (IV) an. Die IV-Stelle Nidwalden traf erwerbliche und medizinische Abklärungen. Sie gewährte sodann als Frühinterventionsmassnahme ein dreimonatiges Praktikum als Allrounder und in der Folge Arbeitsvermittlung. Mit Verfügung vom 26. Januar 2015 verneinte die IV-Stelle einen Anspruch auf eine Invalidenrente, da der Invaliditätsgrad lediglich 31 % betrage.
B.
A._ erhob Beschwerde mit dem Rechtsbegehren, in Aufhebung der Verfügung vom 26. Januar 2015 seien ab 1. Mai 2014 eine ganze Invalidenrente, eventuell eine halbe Invalidenrente und berufliche Massnahmen, zuzusprechen. Die IV-Stelle beantragte, das Eventualbegehren sei insofern gutzuheissen, dass ab 1. Mai 2014 eine halbe Invalidenrente zugesprochen werde. Das Verwaltungsgericht des Kantons Nidwalden hiess die Beschwerde teilweise gut, hob die Verfügung vom 26. Januar 2015 auf und stellte fest, A._ habe ab 1. Mai 2014 Anspruch auf eine halbe Invalidenrente. Es auferlegte sodann die Gerichtskosten von Fr. 800.- je hälftig den Parteien und verpflichtete die IV-Stelle, dem Versicherten eine Parteientschädigung von Fr. 2'066.50 zu bezahlen (Entscheid vom 11. April 2016).
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt A._, der vorinstanzliche Entscheid sowie die Verwaltungsverfügung vom 26. Januar 2015 seien aufzuheben und es sei ab 1. Mai 2014 eine ganze Invalidenrente zuzusprechen. Sodann sei die Verwaltung zu verpflichten, die gesamten Gerichtskosten des kantonalen Verfahrens zu tragen und dem Versicherten für dieses eine ungekürzte Parteientschädigung von Fr. 5'596.45 auszurichten.
Die IV-Stelle schliesst auf Abweisung der Beschwerde. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzungen gemäss Art. 95 und 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), nur die geltend gemachten Vorbringen, falls allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.6 S. 280; vgl. auch <ref-ruling> E. 1 S. 236; <ref-ruling> E. 1.1 S. 137 f.).
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann deren Sachverhaltsfeststellung nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>).
2.
Streitig ist in der Hauptsache, ob das kantonale Gericht bei der Beurteilung des ab 1. Mai 2014 bestehenden Rentenanspruchs Bundesrecht verletzte.
Im angefochtenen Entscheid sind die Bestimmungen und Grundsätze zu den Begriffen Invalidität und Erwerbsfähigkeit, zum nach dem Grad der Invalidität abgestuften Anspruch auf eine Invalidenrente der IV (mit dem hiefür mindestens erforderlichen Invaliditätsgrad von 40 %), zur Bestimmung des Invaliditätsgrades mittels Einkommensvergleich, zur Aufgabe von Arzt und Ärztin bei der Invaliditätsbemessung, zum Untersuchungsgrundsatz und zur Beweiswürdigung, insbesondere bezüglich ärztlicher Berichte und Gutachten, zutreffend dargelegt. Darauf wird verwiesen.
2.1. Das kantonale Gericht hat erkannt, der Versicherte sei aus medizinischer Sicht in einer angepassten Tätigkeit zu 75 % arbeitsfähig. Zumutbar seien leichte bis mittelschwere wechselbelastende Tätigkeiten ohne andauerndes Stehen oder Sitzen, mit Heben oder Tragen von Lasten von gelegentlich bis 10 kg, repetitiv bis 5 kg, ohne repetitives Besteigen von Leitern, bei einer Leistungseinschränkung von 10 bis 20 % für vermehrte Pausen. Ausgehend von diesem Belastungsprofil sei ein Einkommensvergleich vorzunehmen. Das im Gesundheitsfall mutmasslich erzielte Einkommen (Valideneinkommen) sei gestützt auf den zuletzt erzielten Lohn auf Fr. 81'435.- und das trotz gesundheitlicher Beeinträchtigung zumutbarerweise erzielbare Einkommen (Invalideneinkommen) gestützt auf Tabellenlöhne auf Fr. 39'790.- festzusetzen. Das ergebe einen Invaliditätsgrad von 51 %, was den Anspruch auf eine halbe Invalidenrente begründe.
Der Beschwerdeführer macht geltend, es sei ihm, insbesondere wegen seines Alters, nicht zumutbar, die gegebene Restarbeitsfähigkeit noch zu verwerten. Es sei daher zu Unrecht ein zumutbares Invalideneinkommen angerechnet worden. In diesem Zusammenhang werden auch die medizinischen Abklärungen und die daraus gezogenen Schlüsse zur Arbeitsfähigkeit beanstandet.
2.2. Gerügt wird vorab, es sei nicht rechtsgenüglich abgeklärt worden, inwiefern eine Teilerwerbstätigkeit medizinisch zumutbar sein solle. So sei der Versicherte bis heute nicht medizinisch begutachtet worden.
Das kantonale Gericht hat sich mit diesen Vorbringen auseinandergesetzt und ist zum Ergebnis gelangt, sie seien unbegründet. Es hat dabei die Arztberichte und den "Bericht Frühintervention" vom 31. März 2014 gewürdigt und dargelegt, weshalb es diese Akten als vollständige, verlässliche Entscheidungsgrundlage beurteilt und daraus die genannten Folgerungen zur Restarbeitsfähigkeit zieht. Die Vorinstanz hat zudem begründet, weshalb sie entgegen der Auffassung des Beschwerdeführers stark divergierende Befunde verneint und auch keinen Anlass für eine versicherungsexterne medizinische Begutachtung sieht.
Was in der Beschwerde vorgebracht wird, lässt diese Sachverhaltsfeststellungen nicht als offensichtlich falsch oder in anderer Weise bundesrechtswidrig erscheinen. Der Versicherte beschränkt sich im Wesentlichen darauf, seine vorinstanzlichen Vorbringen zu wiederholen. Er legt aber nicht nachvollziehbar dar, inwiefern das kantonale Gericht im Sinne seiner Rügen den Untersuchungsgrundsatz, das Willkürverbot oder andere bundesrechtliche Regeln verletzt haben soll. Das gilt auch hinsichtlich der Beurteilung des medizinisch gegebenen Belastungsprofils. Die Einwände gegenüber einer Beurteilung durch den Regionalen Ärztlichen Dienst (RAD) führen zu keinem anderen Ergebnis. Diese lässt sich ohne Weiteres mit den weiteren medizinischen Akten vereinbaren, insbesondere auch mit der Einschätzung des Dr. med. C._, auf den sich der Versicherte selber beruft. Es liegt auch kein Widerspruch in den RAD-ärztlichen Aussagen vor, welcher die vorinstanzlichen Erwägungen in Frage stellen könnte oder weitere Abklärungen erforderte.
2.3. Der Versicherte wendet weiter ein, die Vorinstanz habe bei der Beurteilung, ob die Restarbeitsfähigkeit mit Blick auf sein Alter noch verwertbar sei, zeitlich zu Unrecht auf den April 2014 abgestellt.
Der Einwand ist unbegründet. Aufgrund der Akten (u.a. Bericht des Dr. med. C._ vom 11. März 2014) hat das kantonale Gericht zu Recht geschlossen, dass im April 2014 die medizinische Zumutbarkeit einer (Teil-) Erwerbstätigkeit feststand. Auf diesen Zeitpunkt ist daher bei der Prüfung, ob die Restarbeitsfähigkeit unter dem Gesichtswinkel des fortgeschrittenen Alters verwertbar ist, abzustellen (vgl. <ref-ruling> E. 3.3 f. S. 461 f. und seitherige Urteile). Dass der RAD erst später ein Zumutbarkeitsprofil umschrieb, ändert hieran entgegen der in der Beschwerde vertretenen Auffassung nichts. Abgesehen davon erfolgte dies bereits mit der RAD-ärztlichen Beurteilung vom 16. Juni 2014 und damit zeitlich nahe zum von der Vorinstanz bestimmten Stichtag. In der weiteren Stellungnahme vom 27. November 2014 hielt der RAD, ohne dass neue Gesichtspunkte hinzugekommen wären, im Wesentlichen an der früheren Einschätzung fest.
2.4. Der Beschwerdeführer macht sodann geltend, wegen seines Alters, seiner beruflichen Fähigkeiten und der gesundheitlichen Beeinträchtigung sei die Restarbeitsfähigkeit wirtschaftlich nicht verwertbar.
Die Vorinstanz hat sich mit diesen Einwänden auseinandergesetzt und sie für unbegründet erachtet. Sie hat im Wesentlichen erwogen, der Versicherte sei ab April 2014in einer angepassten Tätigkeit zu 75 % arbeitsfähig gewesen. Damals sei er 60 Jahre und 2 Monate alt gewesen. Bis zur ordentlichen Pensionierung sei noch eine Restaktivitätsdauer von gut 4 Jahren und 10 Monaten verblieben. Der ausgeglichene Arbeitsmarkt biete Stellen f ür Arbeitssuchende, welche das Alter, die beruflichen Voraussetzungen und das zumutbare Belastungsprofil des Beschwerdeführers aufwiesen. In solchen Tätigkeiten sollte der Umstellungs-, Schulungs- oder Einarbeitsaufwand gering sein, zumal bei der Bestimmung des Invalideneinkommens trotz langjähriger Tätigkeit als Koch nur auf das Kompetenzniveau 1 mit einfachen und repetitiven Arbeiten abgestellt worden sei. Unter Berücksichtigung sämtlicher gesundheitlicher und beruflicher Ressourcen sei von einer genügenden Vermittelbarkeit für zumutbare Verweisungstätigkeiten auszugehen.
Diese Beurteilung entspricht in allen Teilen Gesetz und Praxis. Was der Beschwerdeführer vorbringt, rechtfertigt keine andere Betrachtungsweise. Aus Art. 14a ELV ergibt sich nicht, dass ab dem 60. Altersjahr keine hypothetische Erwerbstätigkeit mehr anzurechnen wäre. Der Versicherte beschränkt sich ansonsten im Wesentlichen darauf, seine vorinstanzlichen Vorbringen zu wiederholen. Diese hat das kantonale Gericht jedoch überzeugend entkräftet. Hervorzuheben ist namentlich, dass die zur Bestimmung des Invalideneinkommens in Betracht gezogenen einfachen und repetitiven Tätigkeiten keine fachspezifische Berufsausbildung oder -erfahrung voraussetzen. Es trifft auch nicht zu, dass die Vorinstanz bei der Bestimmung des Invalideneinkommens die Tätigkeiten als Koch und Konditor als angepasst betrachtet hat. Sodann lässt entgegen der in der Beschwerde vertretenen Auffassung die bundesgerichtliche Praxis nicht den Schluss zu, eine Erwerbstätigkeit im Rahmen der hier gegebenen Restarbeitsfähigkeit sei aufgrund des Alters des Versicherten nicht zumutbar. Das Bundesgericht hat vielmehr verschiedentlich bei in etwa vergleichbarer Ausgangslage - teils lagen sogar höhere gesundheitliche Beeinträchtigungen als hier vor - entschieden, der versicherten Person sei es zumutbar, die Restarbeitsfähigkeit trotz ihres Alters wirtschaftlich zu verwerten (vgl. etwa Urteile 8C_910/2015 vom 19. Mai 2016; 9C_168/2015 vom 13. April 2016; 9C_134/2016 vom 12. April 2016; 8C_345/2013 vom 10. September 2013; 9C_918/2008 vom 28. Mai 2009).
2.5. Das Valideneinkommen und das von den erwähnten Prämissen ausgehende Invalideneinkommen sind im Übrigen nicht umstritten. Gleiches gilt für den Vergleich der Einkommen mit dem Ergebnis eines Invaliditätsgrades von 51 %. Damit bleibt es beim Anspruch auf eine halbe Invalidenrente (<ref-law>). Die Beschwerde ist diesbezüglich unbegründet.
3.
Streitig und zu prüfen bleiben die Kosten- und Entschädigungsfolgen gemäss dem vorinstanzlichen Entscheid.
Die Vorinstanz hat die Gerichtskosten auf Fr. 800.- angesetzt und je hälftig den Parteien auferlegt. Sie hat sodann - in Kürzung der anwaltlichen Kostennote - die von ihr als prozessnotwendig erachteten Anwaltskosten des Versicherten auf Fr. 4'133.- festgesetzt und die IV-Stelle verpflichtet, diesem die Hälfte dieses Betrags als Parteientschädigung auszurichten. Die jeweils hälftige Aufteilung bei Gerichts- und Anwaltskosten hat das kantonale Gericht mit dem Prozessergebnis begründet. Der Versicherte habe im Beschwerdeverfahren (nur) teilweise obsiegt, indem ihm anstatt der beantragten ganzen eine halbe Rente zugesprochen worden sei.
Der Beschwerdeführer beantragt, der IV-Stelle seien sämtliche Gerichtskosten und die ganze Parteientschädigung aufzuerlegen. Dass er nur teilweise obsiegt habe, rechtfertige nach der bundesgerichtlichen Rechtsprechung keine andere Kostenverteilung. Die Parteientschädigung sei überdies auf Fr. 5'596.45 festzusetzen.
3.1. Nach <ref-law> hat die obsiegende Beschwerde führende Person Anspruch auf Ersatz der Parteikosten. Diese werden vom Versicherungsgericht festgesetzt und ohne Rücksicht auf den Streitwert nach der Bedeutung der Streitsache und nach der Schwierigkeit des Prozesses bemessen.
3.1.1. Ist das Quantitativ einer Leistung streitig, rechtfertigt eine "Überklagung" nach der in Rentenangelegenheiten ergangenen Rechtsprechung eine Reduktion der Parteientschädigung nur, wenn das ziffernmässig bestimmte Rechtsbegehren den Prozessaufwand beeinflusst hat. Bildet beispielsweise ein invalidenversicherungsrechtlicher Rentenanspruch Anfechtungs- und Streitgegenstand, führt demgemäss der Umstand allein, dass im Beschwerdeverfahren abweichend von dem auf eine ganze oder zumindest eine höhere Rente gerichteten Rechtsbegehren keine ganze oder aber eine geringere Rente als beantragt zugesprochen wird, noch nicht zu einer Reduktion der Parteientschädigung (Urteile 9C_94/2010 vom 26. Mai 2010 E. 4.1; 9C_672/2008 vom 23. Oktober 2008 E. 5.3.1; 8C_471/2007 vom 1. Februar 2008 E. 3.2 [zitiert in: Anwaltsrevue 2008 S. 244]; je mit Hinweisen, u.a. auf <ref-ruling> E. 2c S. 407; vgl. auch SVR 2011 IV Nr. 38 S. 112, 9C_580/2010 E. 4.1 mit Hinweisen; Urteil 9C_288/2015 vom 7. Januar 2016 E. 4.2).
Im vorliegenden Fall bestehen keine Anhaltspunkte dafür, dass der Prozessaufwand des Versichertenanwaltes höher ausfiel, weil eine ganze statt der zugesprochenen halben Rente beantragt wurde. Im Lichte der dargelegten Grundsätze besteht daher Anspruch auf eine Parteientschädigung in vollem Umfang. Die Beschwerde ist diesbezüglich gutzuheissen.
3.1.2. Das Bundesgericht prüft frei, ob die vorinstanzliche Festsetzung der Parteientschädigung den in <ref-law> statuierten bundesrechtlichen Anforderungen genügt, darüber hinaus nur, ob die Anwendung des kantonalen Rechts zu einer in der Beschwerde substanziiert gerügten (<ref-law>) Verfassungsverletzung geführt hat, wegen seiner Ausgestaltung oder aufgrund des Ergebnisses im konkreten Fall. Dabei fällt praktisch nur das Willkürverbot in Betracht (<ref-law>); es muss nicht nur die Begründung, sondern auch das Ergebnis unhaltbar sein. Das Bundesgericht hebt die Festsetzung eines Anwaltshonorars nur auf, wenn sie ausserhalb jedes vernünftigen Verhältnisses zu den mit Blick auf den konkreten Fall notwendigen anwaltlichen Bemühungen steht und in krasser Weise gegen das Gerechtigkeitsgefühl verstösst (SVR 2016 IV Nr. 14 S. 43, 8C_11/2016 E. 3.2 mit Hinweisen; vgl. auch SVR 2016 UV Nr. 24 S. 75, 8C_354/2015 E. 9.2.2; je mit Hinweisen).
Der Beschwerdeführer beschränkt sich darauf, einen höheren Stundenaufwand seines Anwalts geltend zu machen, ohne substantiiert darzutun, inwiefern die Vorinstanz diesbezüglich in Willkür verfallen sein soll. Er macht sodann geltend, die Vorinstanz habe diesbezüglich ihren Entscheid ungenügend begründet und damit seinen Anspruch auf rechtliches Gehör nach Art. 29 bs. 2 BV verletzt. Die Rüge ist unbegründet. Das kantonale Gericht hat hinreichend klar dargelegt, weshalb es lediglich den Stundenaufwand im Rahmen der zugesprochenen Parteientschädigung für gerechtfertigt hält. Eine sachgerechte Anfechtung des Entscheides war damit möglich (vgl. SVR 2015 IV Nr. 30 S. 92, 9C_598/2014 E. 6.3 mit Hinweisen). Die Beschwerde ist in diesem Punkt abzuweisen.
3.2. Die Beschwerde ist auch bezüglich der Verteilung der Gerichtskosten unbegründet. Die obzitierte Rechtsprechung zur Parteientschädigung ist hier nicht anwendbar (erwähnte Urteile 9C_94/2010 E. 4.3 und 9C_672/2008 E. 5.2.1 [zusammengefasst in: SZS 2009 S. 133]). In der Beschwerde wird nicht dargelegt, inwiefern der vorinstanzliche Entscheid dennoch Bundesrecht verletzen soll. Der geltend gemachte Umstand, dass die IV-Stelle verfügungsweise einen Rentenanspruch gänzlich verneint und im Beschwerdeverfahren den Anspruch auf eine halbe Rente anerkannt hat, lässt nicht auf eine solche Rechtsverletzung schliessen.
4.
Der Beschwerdeführer obsiegt in einem vergleichsweise untergeordneten Punkt. Im Übrigen, insbesondere in der im Vordergrund stehenden Rentenfrage, unterliegt er. Dies rechtfertigt, die Gerichtskosten zu drei Vierteln ihm sowie zu einem Viertel der IV-Stelle aufzuerlegen (<ref-law>). Dementsprechend hat der Beschwerdeführer Anspruch auf eine reduzierte Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Der Entscheid des Verwaltungsgerichts Nidwalden, Sozialversicherungsrechtliche Abteilung, vom 11. April 2016 wird in Dispositiv-Ziffer 4 insoweit abgeändert, als die dem Beschwerdeführer zu bezahlende Parteientschädigung auf Fr. 4'133.- festgesetzt wird. Im Übrigen wird die Beschwerde abgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden zu Fr. 600.- dem Beschwerdeführer und zu Fr. 200.- der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 700.- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Verwaltungsgericht Nidwalden, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 2. November 2016
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Maillard
Der Gerichtsschreiber: Lanz