Main content

## Computer science

# 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[0]`

or `highHalf[0]`

. (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[0]`

or `highHalf[0]`

into `array[p]`

. In our example, `highHalf[0]`

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[0]`

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[0]`

) or the first untaken element in `highHalf`

(`highHalf[1]`

). With one comparison, we determine that `lowHalf[0]`

is smaller, and so we copy it into `array[k]`

and increment `k`

and `i`

:Next, we compare

`lowHalf[1]`

and `highHalf[1]`

, determining that we should copy `highHalf[1]`

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:

- Copy each element in
`array[p..r]`

into either`lowHalf`

or`highHalf`

. - 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`

. - 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?(6 votes)- 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.(18 votes)

- 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){

...

}

...

};

Thank you in advance!(5 votes)- 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(7 votes)

- 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]);(3 votes)- 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(13 votes)

- 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){

...

}

};

Thanks for your help!(4 votes)- The problem is the conditions in the 2nd and 3rd while loops.

They will not always work because the size of the lowHalf and highHalf arrays will not always be equal.(5 votes)

- Earlier we learned about insertion sort. Would the efficiency or complexity be any different if we did NOT use "temporary arrays", but instead simply:

- insertion sort the already-sorted lowHalf into the already-sorted highHalf?(3 votes)- 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)

Hope this answers your question(5 votes)

- 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!(3 votes)- Depending on the array being merged, either the 2nd or 3rd while loop won't be entered. There is probably a mistake in the one that is not being used (it's not being used so you don't see a problem in the output). Double check that you are using the correct indexes.(4 votes)

- I finished my code, but I am curious about why there needs to be a "++" after the letter?

array[k++] = lowHalf[i++];(2 votes)- This is the same as saying:

array[k] = lowHalf[i]

k++

i++

you need to increment both k and i within the loop, your notation just combines the steps into one line of code(1 vote)

- 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 array

var 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]);(3 votes)- It works for me. Which array with the two same elements were you trying to merge ?(2 votes)

- 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?(2 votes)
- 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(3 votes)

- Is it the basic learning of computer science. here var , array, ()small brackets{}big brackets[] are learned. Where to start if i dont know about what is computer science i am diploma in mechanical. I wanna start learning this where i can understand c html css.Please help(1 vote)
- Before learning computer science, you will want learn programming:

Here is a JavaScript course:

https://www.khanacademy.org/computing/computer-programming/programming

If you want to learn html/css try this course:

https://www.khanacademy.org/computing/computer-programming/html-css

For a course in C (not on khan academy) try:

https://www.youtube.com/watch?v=2NWeucMKrLI&list=PL6gx4Cwl9DGAKIXv8Yr6nhGJ9Vlcjyymq(5 votes)