How can I manipulate an array to make the largest number?

The idea of @Nate Kohl is very good. I just implemented a Java version using quicksort. Here it is:

import java.util.Random;

public class Sort_MaxConcatenation {
    private Random r = new Random();

    public void quicksort_maxConcatenation(int[] a, int begin, int end) {
        if (begin < end) {
            int q = partition(a, begin, end);
            quicksort_maxConcatenation(a, begin, q);
            quicksort_maxConcatenation(a, q + 1, end);
        }
    }

    private int partition(int[] a, int begin, int end) {
        int p = begin + r.nextInt(end - begin + 1);
        int t1 = a[p];
        a[p] = a[end];
        a[end] = t1;

        int pivot = t1;
        int q = begin;
        for (int i = begin; i < end; i++) {
            if (compare_maxConcatenation(a[i], pivot) > 0) {
                int t2 = a[q];
                a[q] = a[i];
                a[i] = t2;
                q++;
            }
        }
        int t3 = a[q];
        a[q] = a[end];
        a[end] = t3;

        return q;
    }

    private int compare_maxConcatenation(int i, int j) {
        int ij = Integer.valueOf(String.valueOf(i).concat(String.valueOf(j)));
        int ji = Integer.valueOf(String.valueOf(j).concat(String.valueOf(i)));
        if (ij > ji)
            return 1;
        else if (ij == ji)
            return 0;
        return -1;
    }

    public static void main(String[] args) {

        int[] a = new int[]{56, 5, 4, 94, 9, 14, 1};
        Sort_MaxConcatenation smc = new Sort_MaxConcatenation();
        smc.quicksort_maxConcatenation(a, 0, a.length-1);
        for(int i = 0;i < a.length;i++) {
            System.out.print(a[i]);
        }
    }
}

I would use the following function to sort them

class Kakira {

    static int preferred(int a, int b) {
        if(a == b) return a; // doesn't matter which
        String sa = a+"";
        String sb = b+"";

        for(int i = 0; i < sa.length() && i < sb.length(); i++) {
            char ca = sa.charAt(i);
            char cb = sb.charAt(i);
            if(ca < cb) return b;
            if(ca > cb) return a;
        }
        // we reached here - the larger one must start with the smaller one
        // so, remove the small one from the start of the small one, and
        // that will tell us which is most appropriate.
        if(a < b) {
            String choppedB = sb.substring(sa.length());
            if(preferred(Integer.parseInt(choppedB),a) == a) 
                return a;
            else
                return b;
        }
        else {
            String choppedA = sa.substring(sb.length());
            if(preferred(Integer.parseInt(choppedA),b) == b) 
                return b;
            else
                return a;
        }
    }

    // using a very simple sort because I'm being lazy right now
    public static void sort(int[] data) {
        while(!isSorted(data)) {
            for(int i = 0; i < data.length - 1; i++) {
                int a = data[i];
                int b = data[i+1];
                int p = preferred(a,b);
                if(p == b) {
                    data[i] = b;
                    data[i+1] = a;
                }
            }
        }
    }

    public static boolean isSorted(int[] data) {
        for(int i = 0; i < data.length - 1; i++) {
            int a = data[i];
            int b = data[i+1];
            int p = preferred(a,b);
            if(p != a) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] data = new int[]{9,1,95,17,5};
        sort(data);
        for(int i : data) System.out.print(i);