[Resolvido] Inserir item em índice certo de um ArrayList ordenado

Por que você não cria um pequeno objeto, contendo o elemento da primeira lista e seu índice?

Crie a segunda lista desse objeto e ordene. Assim vc vai automaticamente ter o índice na primeira lista.

Bom, obviamente não vou questionar por que é que você usa um ArrayList em vez de um TreeSet, porque provavelmente você quer também elementos com a mesma chave, o que o TreeSet não aceita (ele não aceita mais de um elemento com a mesma chave, como um MultiSet do C++).
Então você simplesmente poderia fazer algo assim:
EDIT - (Implementação da sugestão que o ViniGodoy deu acima.)

import java.util.*;

class Pair<T, U> {
    public T first;
	public U second;
	public Pair(T t, U u) { first = t; second = u; }
	public String toString() { return "(" + first + "," + second + ")"; }
}

class TesteIndices {
    public static void main (String[] args) {
		List<Integer> desordenado = new ArrayList<Integer>();
		desordenado.addAll (Arrays.asList (new Integer[]{
			3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7
		}));
		System.out.println ("Array original:");
		System.out.println (desordenado);
		// Vamos criar um array contendo os elementos do array original, e
		// os índices desses elementos. Então vamos ordenar esse array
		// segundo os valores dos elementos. Para saber a posição original,
		// basta pegar os índices.
		List<Pair<Integer, Integer>> ordenadoEIndice = new ArrayList<Pair<Integer,Integer>>();
		for (int i = 0; i < desordenado.size(); ++i) {
			ordenadoEIndice.add (new Pair<Integer, Integer> (desordenado.get(i), i));
		}
		System.out.println ("Antes da ordenação:");
		System.out.println (ordenadoEIndice);
		Collections.sort (ordenadoEIndice, new Comparator<Pair<Integer, Integer>>() {
			public int compare (Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {
				return p1.first.compareTo (p2.first);
			}
		});
		System.out.println ("Depois da ordenação:");
		System.out.println (ordenadoEIndice);
		for (int i = 0; i < desordenado.size(); ++i) {
		System.out.printf ("A posição original do elemento [%d] = %d era %d%n", 
		    i, ordenadoEIndice.get(i).first, ordenadoEIndice.get(i).second);
		}
	}
}

Estou dando um exemplo com Integer, mas obviamente você pode usar outro tipo de objeto.

ViniGodoy:

Por que você não cria um pequeno objeto, contendo o elemento da primeira lista e seu índice?

Crie a segunda lista desse objeto e ordene. Assim vc vai automaticamente ter o índice na primeira lista.

ViniGodoy,
Eu quero é descobrir o índice, na segunda lista, de cada item da primeira que foi adicionada à aquela. Entendeu?
Eu descobri o método Collections.binarySearch, parece que vai me ajudar.
Vocês já utilizaram-o? Se sim, o desempenho é bom?

Obrigado mais uma vez pela ajuda.

Vamos supor que você tenha os elementos

lista[0] = C; lista[1] = A; lista[2] = B;

Após ordenar, o que você quer obter?

ViniGodoy:

Vamos supor que você tenha os elementos

lista[0] = C;
lista[1] = A;
lista[2] = B;

Após ordenar, o que você quer obter?

listaA[0] = C;
listaA[1] = A;
listaA[2] = B;

listaB[0] = D;
listaB[1] = F;
listaB[2] = E;

Eu irei adicionar os itens da listaB à listaA.
Após a adição irei ordenar a listaA.
Após a ordenação eu quero saber em quais índices os elementos da listaB foram adicionados à listaA.
Mas eu quero fazer isso sem ter que iterar na listaB e dar um listaA.indexOf para cada item.
Entendeu?

Obrigado pela atenção.

1. Copie os elementos da Lista A para um Set;
2. Adicione os elementos da lista B um a um nesse set. Quando o método add retornar true, é pq foi possível adicionar. Quando retornar false, é pq não conseguiu.

ViniGodoy:

1. Copie os elementos da Lista A para um Set;
2. Adicione os elementos da lista B um a um nesse set. Quando o método add retornar true, é pq foi possível adicionar. Quando retornar false, é pq não conseguiu.

ViniGodoy,
todos os itens da listaB serão adicionados à listaA. O que eu quero saber é em qual índice da listaA cada um foi adicionado. Esta ordenação é definida por um Comparator que eu implementei.

Obrigado pela atenção.

É, esse é o caso de se fazer uma busca binária mesmo, já que A se encontra ordenado.

ViniGodoy:

É, esse é o caso de se fazer uma busca binária mesmo, já que A se encontra ordenado.

Valeu ViniGodoy. A busca binária funcionou. Antes de eu adicionar cada item à lista eu faço uma busca binária que me informa em qual índice o item deve ser adicionado, se este não estiver na lista.

Muito obrigado pela ajuda galera.

Resolvendo o tópico.