Before you read the problem: No, I'm not trying to get you to write code for me, I just want a few pointers
I have a problem with a MergeSort algorithm I'm writing up. The specifications of the code state that I can only use ONE ArrayList for the act of merging. For example:
With an ArrayList of [5, 1, 3, 9, 2], I would recursively split the list up into
- [5, 1, 3] and [9, 2]
- I would split each of these sub lists AGAIN into:
- [5, 1] and [3] ---------- and [9] and [2];
Now, I would sort the arrayList [5, 1] into [1, 5] and then I would have one whole array containing the numbers:
- [1, 5, 3, 9, 2]
Remember, at this point, I have not created ANY new ArrayLists, I have just sorted within the small sublists that I have. So, going back to recursion, I would then merge the list with [1, 5] with the list [3]. Now, how would I go about doing something like that without having to create a brand new ArrayList to store temporary information?
Anyways, once I have [1, 3, 5, 9, 2], I would then sort out the second sublist, [9, 2], and get [1, 3, 5, 2, 9]. Then I would need to "virtually" merge [1, 3, 5] and [2, 9] to get [1, 2, 3, 5, 9]. How would I go about "virtually" merging these lists (in essence, shifting indices over without having to create a new ArrayList).
This is the code I have so far:
int counterFromStart = first;
int counterFromMid = mid + 1;
while (counterFromStart < counterFromMid && (counterFromMid <= last)){
if (a.get(counterFromStart).compareTo(a.get(counterFromMid)) > 0){
Comparable temp = a.get(counterFromStart);
a.set(counterFromStart, a.get(counterFromMid));
a.set(counterFromMid, temp);
counterFromMid++;
} else {
counterFromStart++;
}
}
Also, I have solved this lab in a different way, but not with the method of merging:
With each sublist, I ran through it with insertionSort to sort the two sublists, but again, this is not what "merging" really is: My code, for that method however, is below:
for (int outer = first + 1; outer <= last; outer++){
int positionInSubList = outer;
Comparable insertObject = a.get(positionInSubList);
while (positionInSubList > 0 && a.get(positionInSubList - 1).compareTo(insertObject) > 0){
a.set(positionInSubList, a.get(positionInSubList - 1));
positionInSubList--;
}
a.set(positionInSubList, insertObject);
}
