The Mendicant Bug

Suppose you have an array of floating point numbers with each index into the array being an id number corresponding to some external data structure. You want to sort this array, but in doing so you would destroy the references to the id numbers, since the indexes of the array would no longer correspond to the correct id numbers in the external data structure. For example, let’s say we are dealing with customers of a store and each value in the array is their current balance.

balances = {25.61, 13.45, 89.75, 21.2, 96.50}

Each index in the balances array corresponds to an index in some other array, say:

names = {"Marjory Stewart-Baxter", "Hubert Cumberdale", "Barbara Logan-Price", "Jeremy Fisher", "Mable"}

If we were to merely sort the balances array in descending order, the result would be that the balance of $96.50 would no longer correspond to Mable but to Marjory Stewart-Baxter. Marjory hates Mable enough already, we wouldn’t want her having to pay her bills, as well. Of course, an easy solution would be to use a Map with the name of the person as the key and the balance as the value. The problem comes in that maps are slower to access and consume more memory than arrays, so could be less desirable in situations where speed and memory are important.

In Python, it is easy to sort two lists of this kind. Make each value in the list a tuple (balance, name) and then use the built in sort function:

balnames = zip(balances, names)
balnames.sort()

However, in Python a list does not an array make. Memory consumption can get messy if you are using complicated structures (especially dictionaries). Even if you’re using only tuples of primitives, you consume more memory than a simple array would. I’ve been doing some Java coding over the past few days and ran into this problem. My solution is an implementation of merge sort that sorts both the array of values and keeps track of the indexes in a separate array. Memory consumption is still not optimal, since merge sort is O(n) in memory and keeping track of the indexes doubles that again.

/**
 * Modified merge sort algorithm for sorting an array
 * in descending order while keeping track of indexes.
 *
 * @param indexes array of the original indexes for items in the data array
 * @param data array of the values that the array will be sorted according to (doubles)
 */
public static void mergeSort(int [] indexes, double [] data) {
    if (indexes.length <= 1)
        return;     // stopping condition

    int split = indexes.length / 2;
    int mod = indexes.length % 2;
    int [] indexes_l = new int[split];
    int [] indexes_r = new int[split + mod];
    double [] data_l = new double[split];
    double [] data_r = new double[split + mod];

    // split the arrays into two parts
    for (int i = 0; i < indexes.length; i++) {
        if (i < split) {
            indexes_l[i] = indexes[i];
            data_l[i] = data[i];
        } else {
            indexes_r[i - split] = indexes[i];
            data_r[i - split] = data[i];
        }
    }

    // recursive step
    mergeSort(indexes_l, data_l);
    mergeSort(indexes_r, data_r);

    // now handle merge
    int idx_l = indexes_l.length - 1;
    int idx_r = indexes_r.length - 1;
    while (idx_l >= 0 &amp;&amp; idx_r >= 0) {
        // add the smaller item to the right of the array
        // this produces descending order, in case of tie
        // right side goes in first
        if (data_r[idx_r] > data_l[idx_l]) {
            data[idx_r + idx_l + 1] = data_l[idx_l];
            indexes[idx_r + idx_l + 1] = indexes_l[idx_l];
            idx_l--;
        } else {
            data[idx_r + idx_l + 1] = data_r[idx_r];
            indexes[idx_r + idx_l + 1] = indexes_r[idx_r];
            idx_r--;
        }
    }
    while (idx_l >= 0) {
        data[idx_l] = data_l[idx_l];
        indexes[idx_l] = indexes_l[idx_l];
        idx_l--;
    }
    while(idx_r >= 0) {
        data[idx_r] = data_r[idx_r];
        indexes[idx_r] = indexes_r[idx_r];
        idx_r--;
    }
}

Find any bugs or a better way of doing it? Please let me know.