Я понимаю, что итеративное merge sort можно найти в Интернете, однако созданная мною реализация, похоже, сильно отличается от примеров, которые я видел в Интернете.
Вот что у меня есть.Я реализовал это итеративно, но думаю, что это не правильно, поскольку это не совсем то, что следует за реализацией recursive.
Рекурсивная реализация splits/sorts одна половина, а затем другая, а затем сливается.Эта реализация разбивает / сортирует весь список, а затем объединяет их один за другим с stack.
Мой вопрос заключается в том, является ли это правильной итеративной реализацией?
Я думаю, мне следует использовать queue вместо stack.
public static List<Integer> iterativeMergeSort(List<Integer> nums){
Stack<List<Integer>> stack = new Stack<List<Integer>>();
for (int num : nums) {
stack.push(new ArrayList<Integer>(Arrays.asList(num)));
}
while (stack.size() > 1) {
List<Integer> a = stack.pop();
List<Integer> b = stack.pop();
stack.push(merge(a,b));
}
return stack.pop();
}
public static List<Integer> merge(List<Integer> a, List<Integer> b) {
int i = 0;
int j = 0;
List<Integer> merged = new ArrayList<Integer>();
while (i < a.size() && j < b.size()) {
if (a.get(i) == b.get(j)) {
merged.add(a.get(i));
merged.add(b.get(j));
i++;
j++;
}
else if (a.get(i) < b.get(j)) {
merged.add(a.get(i));
i++;
}
else { //a.get(i) > b.get(j)
merged.add(b.get(j));
j++;
}
}
while (i < a.size()) {
merged.add(a.get(i));
i++;
}
while (j < b.size()) {
merged.add(b.get(j));
j++;
}
return merged;
}