algorithmsortingtimsort

How do I use TimSort to sort by multiple fields?


I have implemented TimSort but I really need to be able to sort by different fields. E.g. sort by field 2, then 1, then 3. I know in general terms how to do this, sort by the next field if the previously given fields to sort by are equal, but I'm looking for a solution that has more detail and in particular for TimSort.


Solution

  • The fact that you sort using several fields has an influence on the comparing function alone, not on the implementation of the sorting algorithm you use.
    To sort objects, you need to be able to compare them. A simple way to do so is to implement a function isSmaller, that takes two objects as arguments, and returns true if the first is smaller than the second.

    The function isSmaller can look like this with the criteria you gave:

    function isSmaller(object1, object2) -> boolean {
        if object1.field2 < object2.field2 {
            return true
        } else if object1.field2 > object2.field2 {
            return false
        } else {                           // equality on first criterion -> check the second
            if object1.field1 < object2.field1 {
                return true
            } else if object1.field1 > object2.field1 {
                return false
            } else {                      // equality again -> check 3rd criterion
                if object1.field2 < object2.field3 {
                    return true
                } else if object1.field2 > object2.field3 {
                    return false
                } else {                 // equality on all criteria -> can return true or false
                    return true
                }
            }
        }
    }
    

    All you have to do then, is to use it to compare your objects in your implementation of Timsort.