If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

## Computer science

### Course: Computer science>Unit 1

Lesson 8: Merge sort

# Linear-time merging

The remaining piece of merge sort is the merge function, which merges two adjacent sorted subarrays, array[p..q] and array[q+1..r] into a single sorted subarray in array[p..r]. We'll see how to construct this function so that it's as efficient as possible. Let's say that the two subarrays have a total of n elements. We have to examine each of the elements in order to merge them together, and so the best we can hope for would be a merging time of \Theta, left parenthesis, n, right parenthesis. Indeed, we'll see how to merge a total of n elements in \Theta, left parenthesis, n, right parenthesis time.
In order to merge the sorted subarrays array[p..q] and array[q+1..r] and have the result in array[p..r], we first need to make temporary arrays and copy array[p..q] and array[q+1..r] into these temporary arrays. We can't write over the positions in array[p..r] until we have the elements originally in array[p..q] and array[q+1..r] safely copied.
The first order of business in the merge function, therefore, is to allocate two temporary arrays, lowHalf and highHalf, to copy all the elements in array[p..q] into lowHalf, and to copy all the elements in array[q+1..r] into highHalf. How big should lowHalf be? The subarray array[p..q] contains q, minus, p, plus, 1 elements. How about highHalf? The subarray array[q+1..r] contains r, minus, q elements. (In JavaScript, we don't have to give the size of an array when we create it, but since we do have to do that in many other programming languages, we often consider it when describing an algorithm.)
In our example array [14, 7, 3, 12, 9, 11, 6, 2], here's what things look like after we've recursively sorted array[0..3] and array[4..7] (so that p, equals, 0, q, equals, 3, and r, equals, 7) and copied these subarrays into lowHalf and highHalf:
The numbers in array are grayed out to indicate that although these array positions contain values, the "real" values are now in lowHalf and highHalf. We may overwrite the grayed numbers at will.
Next, we merge the two sorted subarrays, now in lowHalf and highHalf, back into array[p..r]. We should put the smallest value in either of the two subarrays into array[p]. Where might this smallest value reside? Because the subarrays are sorted, the smallest value must be in one of just two places: either lowHalf or highHalf. (It's possible that the same value is in both places, and then we can call either one the smallest value.) With just one comparison, we can determine whether to copy lowHalf or highHalf into array[p]. In our example, highHalf was smaller. Let's also establish three variables to index into the arrays:
• i indexes the next element of lowHalf that we have not copied back into array. Initially, i is 0.
• j indexes the next element of highHalf that we have not copied back into array. Initially, j is 0.
• k indexes the next location in array that we copy into. Initially, k equals p.
After we copy from lowHalf or highHalf into array, we must increment (add 1 to) k so that we copy the next smallest element into the next position of array. We also have to increment i if we copied from lowHalf, or increment j if we copied from highHalf. So here are the arrays before and after the first element is copied back into array:
We've grayed out highHalf to indicate that it no longer contains a value that we're going to consider. The unmerged part of the highHalf array starts at index j, which is now 1. The value in array[p] is no longer grayed out, because we copied a "real" value into it.
Where must the next value to copy back into array reside? It's either first untaken element in lowHalf (lowHalf) or the first untaken element in highHalf (highHalf). With one comparison, we determine that lowHalf is smaller, and so we copy it into array[k] and increment k and i:
Next, we compare lowHalf and highHalf, determining that we should copy highHalf into array[k]. We then increment k and j:
Keep going, always comparing lowHalf[i] and highHalf[j], copying the smaller of the two into array[k], and incrementing either i or j:
Eventually, either all of lowHalf or all of highHalf is copied back into array. In this example, all of highHalf is copied back before the last few elements of lowHalf. We finish up by just copying the remaining untaken elements in either lowHalf or highHalf:
We claimed that merging n elements takes \Theta, left parenthesis, n, right parenthesis time, and therefore the running time of merging is linear in the subarray size. Let's see why this is true. We saw three parts to merging:
1. Copy each element in array[p..r] into either lowHalf or highHalf.
2. As long as some elements are untaken in both lowHalf and highHalf, compare the first two untaken elements and copy the smaller one back into array.
3. Once either lowHalf or highHalf has had all its elements copied back into array, copy each remaining untaken element from the other temporary array back into array.
How many lines of code do we need to execute for each of these steps? It's a constant number per element. Each element is copied from array into either lowHalf or highHalf exactly one time in step 1. Each comparison in step 2 takes constant time, since it compares just two elements, and each element "wins" a comparison at most one time. Each element is copied back into array exactly one time in steps 2 and 3 combined. Since we execute each line of code a constant number of times per element and we assume that the subarray array[p..q] contains n elements, the running time for merging is indeed \Theta, left parenthesis, n, right parenthesis.
In the next challenge, you'll implement this linear-time merging operation. With the two challenges combined, you'll have implemented the complete merge sort algorithm.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

## Want to join the conversation?

• I feel like I cheated the grader...
[Edited to remove solution for first step]

The code worked OK for the first step, but on the second one, where I used negative numbers and 0, it went haywire.
It wouln't put zero where it had to and a 1 I used also was mislocated. I deleted both of them from my array, (it was [3, 3, -5, -1, 1, 0 14, 5] initially) and then it was properly sorted and the evaluator let me pass.
But I still feel like I did something wrong and just cheated to pass.
Can any one tell me where I was wrong? • No issue with your merge function, but there are issues with how you are trying to use it.

Merge requires the lower half and upper half of the array to be sorted before it is called. If the lower half and upper half aren't initially sorted then it will behave unpredictably.
So for [3, 3, -5, -1, 1, 0 14, 5]:
- the lower half: [3,3,-5,-1] is not sorted
- the upper half: [1,0,14,15] is not sorted
So we shouldn't expect merge to work properly. You might get lucky and it might still end up as a sorted array, but it would just be coincidence.
• Hello,

I'd like to ask for some help or hints! I've been working on the 'Implement Merge' challenge and I got at least somewhere with my code. However, somewhere there must be still be a mistake (or two hehe), because the grader is not passing me onto the second step. I am not getting any oh noes or hints in the program itself, so I find it quite hard to figure out what I have to do. This is my code so far: (only showing the while loops):
[Edited to only show relevant code]
...    while(lowHalf.length !== i && highHalf.length !== j){       ...    }        while(lowHalf.length !== i){        ...    }    while(highHalf.length !== j){        ...    }   ...}; • The code is technically correct, but the conditions you are using are fairly unusual, so the grader isn't expecting them.
e.g. It is unusual to see someone use lowHalf.length !== i instead of i < lowHalf.length

i < lowHalf.length is generally preferred, because it is safer. Here's why:
- lowHalf.length !== i will only stop when i is exactly equal to the length of the array, so if i was ,by accident, larger than the length of the array this condition would pass, and bad things like trying to access elements not in the array could occur ( in a programming language like C or C++ this could have serious consequences)
-on the other hand i < lowHalf.length would fail if , by accident, i was larger than the length of the array, thus preventing potential disaster

Hope this makes sense
• This doesn't work with arrays with 0 but it should I think:

[Edited to show only relevant code]
var narray = [3, 15,  0, 7, 12, 14, 2, 6, 11];merge(narray, 0, Math.floor((0 + narray.length-1) / 2), narray.length-1);println("Array after merging: " + narray);Program.assertEqual(narray, [0, 2, 3, 6, 7, 11, 12, 14, 15]); • Merge needs the lower half and upper half of the arrays to be sorted.
If the upper and lower half are not sorted then merge will not work properly.

Note the following:
array= [3, 7, 12, 14, 2, 6, 9, 11]
the lower half is: [3, 7, 12, 14] (note that it is sorted)
the upper half is: [2, 6, 9, 11] (note that it is sorted)
The lower half and upper half are sorted, so merge works as expected.

Note the following:
narray= [3, 15, 0, 7, 12, 14, 2, 6, 11]
the lower half is: [3, 15, 0, 7, 12] (note that it is NOT sorted)
the upper half is: [14, 2, 6, 11 ] (note that it is NOT sorted)
The lower half and upper half are not sorted, so merge does not work as expected.

Hope this makes sense
• Hello everyone!
I've finished the challenge Implement Merge, but still the grader won't accept it. The result is correct, but still there seems to be something amiss. Is it the ++s? I haven;t used any fix numbers, so I can't seem to get where I am wrong...

This is my code
[Edited to only show relevant code]
    while (...)    {        ...    }       while(i<j) {        ...    }    while (j<i){       ...    }    }; • Earlier we learned about insertion sort. Would the efficiency or complexity be any different if we did NOT use "temporary arrays", but instead simply: • The merge algorithm doesn't care how the lowHalf and highHalf arrays were sorted
It will merge two sorted arrays in O(n)

If you were trying to sort an array by:
- splitting the array into two halves
- insertion sort each half
- merge the two halves together
The complexity would be O(n^2) (which is worse than merge sorts's O(n log n) )
Why ?
Each half has n/2 elements, and sorting n/2 elements using a n^2 algorithm is O(n^2).
O( (n/2)^2) = O( n^2/4 ) = O (n^2) (we drop the constants)

• Has anyone ever finished this task?
The result I get is correct, the array is successfully merged and sorted but I can't go to the next step! • I finished my code, but I am curious about why there needs to be a "++" after the letter?

array[k++] = lowHalf[i++]; • In next challenge, when the array have two same elements, the function will don't work
how can I modify it? thanks in advance! XD

// Takes in an array that has two sorted subarrays,//  from [p..q] and [q+1..r], and merges the arrayvar merge = function(array, p, q, r) {    var lowHalf = [];    var highHalf = [];    var k = p;    var i;    var j;    for (i = 0; k <= q; i++, k++) {        lowHalf[i] = array[k];    }    for (j = 0; k <= r; j++, k++) {        highHalf[j] = array[k];    }    k = p;    i = 0;    j = 0;        // Repeatedly compare the lowest untaken element in    //  lowHalf with the lowest untaken element in highHalf    //  and copy the lower of the two back into array    while (i < lowHalf.length && j < highHalf.length) {        if (lowHalf[i] <= highHalf[j]) {            array[k++] = lowHalf[i++];        } else {            array[k++] = highHalf[j++];        }    }            // Once one of lowHalf and highHalf has been fully copied    //  back into array, copy the remaining elements from the    //  other temporary array back into the array        while (i < lowHalf.length) {        array[k++] = lowHalf[i++];    }        while (j < highHalf.length) {        array[k++] = highHalf[j++];    }    };var array = [3, 7, 12, 14, 2, 6, 9, 11];merge(array, 0,    Math.floor((0 + array.length-1) / 2),    array.length-1);println("Array after merging: " + array);Program.assertEqual(array, [2, 3, 6, 7, 9, 11, 12, 14]);var array2 = [3, 9, 1, 4];merge(array2, 0,    Math.floor((0 + array2.length-1) / 2),    array2.length-1);println("Array2 after merging: " + array2);Program.assertEqual(array2, [1, 3, 4, 9]); • Until I began studying algorithms here, I had always read and heard that you should avoid mutating the original list, array, or collection while performing any sort of logic on it. For instance, I would typically return a copy of the original array here that is sorted. Is there a reason this isn't practiced in these lessons? • There's nothing wrong with functions that mutate their inputs, as long as it is clear to the user that the inputs will be modified. They are used all the time. Of course, there are many cases where the user doesn't want the original inputs modified. In these cases, it would be fairly easy to wrap a function around the mutator function that does the following:
1) make copies of original inputs
2) pass copies of inputs to mutator function
3) return results of mutator function

The reason you wouldn't always make copies of the inputs are:
- making copies consumes memory and takes time
e.g. copying an array requires O(n) space and O(n) time

When writing algorithms you are typically trying to minimize the use of space and time.

Hope this makes sense

P.S. I would be curious to see examples where books have said to avoid using mutators 