The discrete Sugeno integral is an aggregation function particularly suited to aggregation of ordinal inputs. It accounts for inputs interactions, such as redundancy and complementarity, and its learning from empirical data is a challenging optimisation problem. The methods of ordinal regression involve an expensive objective function, whose complexity is quadratic in the number of data. We formulate ordinal regression using a much less expensive objective computed in linear time by the pool-adjacent-violators algorithm. We investigate the learning problem numerically and show the superiority of the new algorithm. © 2019 Wiley Periodicals, Inc.