Is our linked-list-based implementation of merge-sort (Code Fragment 12.3) stable? Explain why or why not. /** Merge

Is our linked-list-based implementation of merge-sort (Code Fragment 12.3) stable? Explain why or why not.

Transcribed Image Text:

/** Merge contents of sorted queues S1 and S2 into empty queue S. */ public static void merge(Queue S1, Queue S2, Queue S, Comparator comp) { 3 while (!S1.isEmpty() && !S2.isEmpty()) { if (comp.compare(S1.first(), S2.first()) < 0) S.enqueue(S1.dequeue( )); else 4 // take next element from S1 6. // take next element from S2 S.enqueue(S2.dequeue( )); } while (!S1.isEmpty()) S.enqueue(S1.dequeue()); while (!S2.isEmpty()) S.enqueue(S2.dequeue( )); } 10 // move any elements that remain in S1 11 12 // move any elements that remain in S2 13 14 15 /** Merge-sort contents of queue. */ public static void mergeSort(Queue S, Comparator comp) { int n = S.size(); if (n < 2) return; // divide Queue S1 = new LinkedQueue<>(); Queue S2 = new LinkedQueue<>(); while (S1.size() < n/2) S1.enqueue(S.dequeue()); while (!S.isEmpty()) S2.enqueue(S.dequeue( )); // conquer (with recursion) mergeSort(S1, comp); mergeSort(S2, comp); // merge results merge(S1, S2, S, comp); } 16 17 18 // queue is trivially sorted 19 20 // (or any queue implementation) 21 22 23 // move the first n/2 elements to S1 24 25 // move remaining elements to S2 26 27 // sort first half // sort second half 28 29 30 // merge sorted halves back into original 31 32