Understanding the custom compare pattern

Sorting a sequence of data arranges them in their natural order, defined by the < and > operators. However, there are some problems that require ordering user-defined or complex data types that do not have inherent ordering. In most cases, to solve these problems, we first define the new data type and then create a comparator to specify the ordering logic for its sorting.

The custom compare pattern is a classification of problems that can be solved using any sorting algorithm with a custom comparator.

In this lesson, we will learn more about using the custom compare technique to solve problems and how to identify a problem as a custom compare pattern problem.

The custom compare technique

Consider an array of integers arr of size N, a user-defined type Entry, and a transformation function t (for example, a function that maps an integer to the pair (value, value * value), as used in the implementations below). The function t maps each value in the array to an instance of the user-defined type Entry. For this example, consider the generic array of values given below.