 
     // Note: keys have not been modified
     // Note: permutation now maps unsorted keys to sorted order
-    
+  
+    // permute the key arrays by the final permuation
+    apply_permutation(lower,  permutation);
+    apply_permutation(middle, permutation);
+    apply_permutation(upper,  permutation);
+
     std::cout << "Sorted Keys" << std::endl;
     for(size_t i = 0; i < N; i++)
     {
-        // p is the index in the *unsorted* arrays of the i-th sorted element
-        int p = permutation[i];
-        std::cout << "(" << upper[p] << "," << middle[p] << "," << lower[p] << ")" << std::endl;
+        std::cout << "(" << upper[i] << "," << middle[i] << "," << lower[i] << ")" << std::endl;
     }
 
     return 0;
 }
+

    }

    // initialize permutation to [0, 1, 2, ... ,N-1]
    thrust::host_vector<int> permutation(N);
    thrust::sequence(permutation.begin(), permutation.end());

    // sort from least significant key to most significant keys

}


template <typename KeyVector, typename PermutationVector>
void apply_permutation(KeyVector& keys, PermutationVector& permutation)
{
    // copy keys to temporary vector
    KeyVector temp(keys.begin(), keys.end());

    // permute the keys
    thrust::gather(keys.begin(), keys.end(), permutation.begin(), temp.begin());
}


thrust::host_vector<int> random_vector(size_t N)
{
    thrust::host_vector<int> vec(N);

    for (size_t i = 0; i < N; i++)
        vec[i] = rand() % 10;

    return vec;
}


