Faits : A. A._ a travaillé dès le 29 avril 1991 au service de la succursale genevoise de B._ SA (ci-après: l'employeuse). Il y a occupé successivement diverses fonctions, dont en dernier lieu celle de "Credit control...", en vertu de laquelle il était chargé notamment de l'encaissement de factures ouvertes, de contacts avec la clientèle en situation de retard de paiement et de représentation de la société pour le recouvrement. Le 13 mai 2013, A._ et l'un de ses collègues ont eu un différend lié à une note de frais dont le premier entendait obtenir le remboursement sans être en mesure de fournir les justificatifs. Ce différend s'est terminé par des lésions corporelles simples au préjudice de A._ (ci-après: l'employé ou le travailleur), dont le collègue a été reconnu coupable par ordonnance pénale du 22 novembre 2013. L'employeuse a auditionné les deux protagonistes et verbalisé leurs déclarations, que les deux intéressés ont signées. L'employé a emporté une copie du procès-verbal, selon lui par mégarde, puis l'a restituée à l'employeuse; celle-ci lui a signalé que s'approprier le document d'autrui était un vol. Le 7 juin suivant, l'employeuse a informé le travailleur qu'elle entendait mettre un terme à leurs rapports de travail, en se référant à l'"altercation" du 13 mai. Par lettre du 11 novembre 2013, l'employeuse lui a signifié son licenciement pour le 11 février 2014. A la demande de l'employé, l'employeuse a motivé sa décision en ces termes le 25 novembre 2013: "non-respect des procédures internes, en particulier de la procédure à suivre en matière de remboursement de frais; violence verbale; disparition/vol de documents de l'enquête interne qui a suivi l'altercation de votre mandant et de l'un de ses collègues". B. Le 31 mars 2014, l'employé a saisi l'autorité de conciliation du Tribunal des prud'hommes du canton de Genève, puis a porté l'action devant ledit tribunal en concluant au paiement de 49'172 fr. 50 à titre d'indemnité pour licenciement abusif et 45'000 fr. à titre d'indemnité pour tort moral. Débouté par jugement du 30 juin 2015, l'employé a déféré cette décision à la Cour de justice du canton de Genève, qui a rejeté son appel par arrêt du 24 février 2016. C. L'employé saisit le Tribunal fédéral d'un recours en matière civile concluant principalement à la réforme de l'arrêt attaqué, en ce sens que l'employeuse soit condamnée à lui payer 49'172 fr. 50 à titre d'indemnité pour licenciement abusif et 45'000 fr. à titre d'indemnité pour tort moral, le tout avec intérêts à 5 % dès le 11 novembre 2013. Subsidiairement, elle requiert le renvoi de l'affaire à l'autorité cantonale pour nouvelle décision au sens des considérants. L'intimée conclut au rejet du recours. L'autorité précédente se réfère à son arrêt.