When you arrive at undoubtedly prestigious sorting algorithms like the mergesort, it is somewhat implied (or at least this is the course taken by nearly all books) you already have some knowledge (not necessarily a deep one) of the previous and simpler class of sorting algorithms: the so called quadratic ones like selection sort and bubble sort.

Mergesort was originally developed by John von Neumann (1903 - 1957), which is quite of a name if you consider he contributed to provide foundations for the quantum statistical mechanics and was even in the Manhattan Project during WW2. So when you think an algorithm is "easy", it is so only because you are served with the eventual result of decades of work by (in this case) a probable genius.
I say this because I find always rather amusing when on newsgroups we see alleged experts play the experts by belittling beginners (or also seasoned developers) who find rightly difficult to grasp the logics of an algorithm: these experts of the efforts of the others, clearly, have no idea of what sweat, what blood, and what tears may have costed to men worth ten millions of them what today they deem "simple" just because they had to endure no toil yesterday in order to invent it out of the blue.

I subsume here a few of the basic points (plus a bit more) made on the above mentioned files about the other sorting algorithms, leaving to you having a look at them if you want or need a more articulated grasping of these premises.

• All sorting algorithms take in an array of arguably disordered values, and obviously enough want to return an ordered one (as for the arbitrary meaning actually attached with the idea of what is order, see the first part of the selection sort file).
• Algorithms like the selection sort and bubble sort are quadratic, which means their codes include a loop nested within another loop.
  
  On the contrary, algorithms like the mergesort are not quadratic.
  This generally implies that non quadratic algorithms are considered faster than the quadratic ones, and yet it does not necessarily hold true: shell sort is quadratic, and yet can be in some circumstances nearly as fast as a merge sort is.
• With a merge sort you have one of the faster (not the fastest though) possible algorithms.
  Yet its main drawback is that whereas in all sorting processes is required to produce no auxiliary arrays in the process (so called sorting in place), yet mergesort in its canonical version produces such auxiliary array.
  Thus, there is in it a space/time trade off, and it is vastly insofar as mergesort requires additional memory space in order to accommodate the auxiliary array it produces (at least an half of the space already occupied by the incoming array to be sorted), that it is not considered the faster or the theoretically most optimal sorting algorithm.
• All sorting algorithms sort insomuch as they perform checks among the values of the incoming array, and reposition them accordingly on whether the compared values are the one bigger or smaller than the other.
  All these comparisons necessarily occur between two and no more than two array entries per round: this is in the nature of the thing itself.
  Though it may appear obvious, yet this is exactly the level where sorting algorithms truly differ: on how they choose from the incoming array these two elements to be compared at each iteration.
  
  The most natural and simplest way to compare an array entries, is to iterate checking the contiguous ones.
  For instance, a selection sort achieves this by starting the innermost loop (being quadratic, as said, its code exhibits two nested loops) at one unit higher than the outermost loop: in this fashion the currently scanned array entry can be compared with the contiguous and previous one by merely subtracting 1 to the loop index - and thus incur in no out of array boundaries exception (this is all detailed better in its dedicated file).
  
  Shellsort takes this one step further: it produces fixed distances, as if measuring rulers, at whose edges the two elements to be compared are picked.
  When these fixed distances, shifting onward, are no longer fit to intercept the remaining array entries (they exceed one edge of the array), these distances get gradually shrunk, and the process repeats among array couples located at a now reduced distance.
  
  Mergesort takes in another turn of the screw: it determines which are the two elements to be compared recursively fractioning by halving the incoming array until it yields arrays composed by one element only: in fact, it is beyond doubt that if you go on halving an array long enough, eventually every branch will output an array of one entry only.
  Also Adam Drozdek in his book about algorithms in Java puts the stress on this: the procedure stops «when the array has less than two elements». This means one.
  
  This fractioning of an array by halving is traditionally called a «Divide And Conquer» algorithm (by the ancient Rome political motto «Divide Et Impera»), whereas what this means is very efficaciously described as:

  The divide-and-conquer-strategy for solving a problem consists of three steps:
  
  1) Divide: the problem is decomposed into subproblems
  2) Conquer: the subproblems are solved
  3) Combine: the solutions of the subproblems are recombined to the solution of the original problem
  
  [source]

  Mergesort then compares among themselves these halved arrays, climbing backward those yielded halves from the smaller ones composed of one entry only, up throughout the previously generated halves, ordering first the smaller fragments, and then reuniting these fragments together in bigger fragments, ordering these latter too, and so on until the one undivided original array (but this time, unlike the original, sorted) is achieved once again.
  
  Therefore, a mergesort is just a different way to devise a ruler that sets defined and shrinking distances (smaller halved fragments obviously have edges separated by smaller distances) whose edges can be grabbed and compared with each other.
  
  These edges still institute comparisons among couples as any other sorting algorithm seems bound to do, only that instead of being contiguous couples like in a selection sort or devised as in a shellsort as the extremes of distances set by numerical values arbitrary chosen within the boundaries of the array length, in a mergesort such distances are located by progressively halving and at each round.
  
  So, this is why a mergesort seems more mindful of a shellsort than of a selection sort, if we want to find out, in an idle moment, the closest instance to mergesort in the field of its quadratic siblings.

Even before I get in the difficult task to make you understand (at least as much -or as little if you prefer- as I did) how a merge sort works, I'd strongly suggest and I'd indicate as immensely beneficial if you have first a look at a graphical animation of it.
It is not necessary that you understand it, but it is highly advisable that you at first and at least get a visual intuition of what shall go on. It shall help.

I think the following graphical animation via a java applet is in the public domain as it has been developed (so it seems after having checked the applet internal signature) by Apple Computer, Inc.
At any rate, under this assumption, I copied it from here.
With this animation you can either:

• Click repeatedly the button «STEP» for a step by step animation.
• Or click once the button «GO» for an uninterrupted animation.
• If you see no controls in the box below, maybe your pc hasn't a java (not a javascript) interpreter installed.
  If so, you will have to manage without this visual example (which I guess can certainly be done: this graphical example is just meant as an useful and yet not indispensable cognitive support).

We have said that each sorting algorithm, in order to sort an array, performs comparisons on two elements (couples) of it per round, and that sorting algorithms differ mainly by how they detect or grab these couples meant to be compared.

We also stated that a mergesort achieves this by dividing the input array into fragments until splinters composed of only one array entries are yielded.

Before entering the details of it, and being more precise about them, let's first see how such recursive fragmentation can be achieved in a divide and conquer setting as mentioned earlier and as pursued by a mergesort.

When we say divide and conquer we mean actually more than just fractioning an array till unary entries: the goal of a divide and conquer is not of reaching the unary arrays where it stops (for the fact it stops there, may be mistaken for a "goal"), but of producing the whole family of halves.

Divide and conquer means achieving that ultimate step of having the single entries, but by gradually halving.
These halves shall have a role and shall be used as well, they will not be just dysfunctionally brushed aside as expendable chattels in view of the eventual "goal" of relinquishing the unary couples to be compared.

Before seeing how these intermediate fragments will play a role, let's see how this fragmentation is achieved and how these just mentioned halved fragments of different lengths could be produced: for what's the point with discussing about halves, if we don't even know how to get them?
That is, in a divide and conquer paradigm, let's deal first with the divide part.

What we want, in a simple example, is producing this: [6,8,3,3,1,4] //SIMPLE (=short) incoming array of unordered values (duplicates allowed of course)
[6,8,3] [3,1,4] //first halves
[6,8] [3] [3,1] [4] //last halves (odds get accommodated producing just lonely entries) The traditional way to achieve that is recursion. I shall describe these processes supposing you're not too well acquainted with these programming traditional features, and yet also seasoned programmers shall find, as they go on, food for their teeth. Mergesort is no nuisance.

WHAT IS RECURSION?

A function is called recursive when in its code it calls in itself again (one or even more times), like a spiral unwinding within.
It is immediately apparent that such a process must first of all determine:

• When it shall stop - or otherwise it goes without saying that a function that calls in itself would go on simply forever if no halting condition is provided.
• Then, it shall have to manipulate the data (particularly the ones included in the exit condition) so to update them before (and after if necessary) the recursive call - otherwise it would be just a meaningless repetitive call to invariant data, which as such would never meet the halting conditions.

//javascript trivial example

function foo(arg){
if(arg > 9){alert(arg); return; /* exit condition */};
++arg; /* update of the value checked in the exit condition: in this pointless function, it just adds 1 */
foo(arg); /* one recursive call */
}

foo(2 /* passed an actual argument value */); //test it!

I do not think it would be appropriate to describe here in all its excruciating details also how recursion works. Yet, when a function invokes itself, what happens is not different from what happens when a function calls in a different function (let's call it foo): nothing that in the code of the caller may be located after the foo function gets executed until foo has completely run.

function dunno(){
foo();
alert('foo has run');/*this is NOT triggered unless foo() has completely run*/
}

If you have programmed a little bit, this should come as no surprise at all for you. It's just normal, functions are procedural entities that execute commands one at a time: nothing that is after gets dealt with until all that is before has not been dealt with.

chinese boxes

Nothing changes, if the called function is the caller itself: all these calls are piled up upon a stack, temporarily "suspended" over there, and only when the exit condition is met, the cascading process triggers a downfall effect that from the last piled call speeds headlong executing all the other piled calls.
This means that a function that calls in itself (and which of course includes an exit condition), will end up queuing itself.

In fact if what is "after" in a code cannot be executed until it has been executed what was "before", and what is before is always the same function, the only thing left to do is to pile up the order of calls of all these "befores", awaiting the moment when an exit condition shall allow factual execution - from top of the pile: think of russian dolls, or of chinese boxes.

This pile is so arranged on computers, that it will also keep track per each stack dish of possible variables carried along whose values may have been updated in the process.
That is, recursion will be able, for each piled element, to keep track of the possible updated values of:

• Parts of code computations that may have been placed before the recursive call and which as such are still suited to be executed, because the temporary interdiction to the immediate execution of code is meant for code portions that are placed after the recursive calls, not before them.
  
  This applies though only as long as such results of the computations are stored in some variable whose scope is wider (maybe global) than that of the recursive function. That is, what I mean is that these calculations, being included before, get executed while recursion is still running, but actually are not stored or kept track of in the pile unless you yourself store them in some external variable.
• Parts of code computations that were placed as contextual to recursion: that is, calculations performed and passed as the recursive calls' arguments.
  This applies always, and its partial results are stored indeed in the recursion queue.

Once the exit condition is met, the recursive function shall fulfill the queue of its own calls, executing them from the last piled towards the first namely in inverse order: this because each recursive round is like establishing that there is something to be done before (and thus to pile), and therefore the highest priority is eventually deduced as to be bestowed upon the call within the last round, and then degrading from that pinnacle along the ladder towards the original base.

Of course this queue (better: stack) generated by a recursion, and whose technical name is activation record, cannot go on piling forever.
All language interpreters and machines allow a maximum of memory slots that can be allocated to accommodate the layers composing such type of stacks (think of available "floors" for a skyscrape), and if this maximum gets exceeded (so called stack overflow: think of a pot that brims when a last cup too much is poured in), the recursion may be forcibly aborted.
This is why at times one may prefer a non recursive version of an algorithm.

It should thus be clear that a function whose task is to divide an incoming array in halves, once it is arranged as recursive namely so to call in itself again, shall further divide each of these halves it itself generated: because such has been its designed task since the beginning, and thus the recursion shall go on halving - until the halting condition is met.
It makes sense, doesn't it? A function that halves an array, if it calls in itself, just goes on doing the same job, and therefore it halves the halves, round after round, till the end where no more halves can be produced.

Let's try a PHP halving snippet, to get a bit closer to the mergesort logics.
It shall determine the exit condition, shall perform the data manipulation, and shall include the recursive call to itself (plus printing some stuff to show what happens): function halves($inputArray){
$middle=floor(sizeof($inputArray)/2); /* $middle shall DECREASE UPON RECURSION while it produces smaller and smaller halves */
if($middle){/* if NOT, no recursion */
      $left=array_slice($inputArray, 0, $middle);
      $right=array_slice($inputArray, $middle);
      print implode(', ', $left).'<br>'.implode(', ', $right).'<br> <br>';
//2 RECURSIVE CALLS:
halves($left);
halves($right);
};
} If applied on an array like [1,2,3,4,5,6,7,8,9,10,11,12], that would print array fragments as halved in the following order (red slices are legacies of the first half -or say of left branches- of the incoming array, blue slices are legacies of the second -or say of right branches): At this stage it should surprise you no longer that recursion is the most traditional way used in a mergesort to halve arrays.

There is now a thing that I want you to notice in the code above.
It was slicing the array, using the php built in function array_slice. Such function extracts fragments (slices) from the array not by removing them but by producing copies.
This obviously requires additional space on disk. Though it is generally not a significant problem in most cases, yet a well done algorithm should also wonder whether it would be possible to achieve the same result (fragments) grabbing the slices not as copies but as removed from the input array (thus using no extra space).
Php has a method that does that (namely removes the segments, and doesn't just copy them), which is called array_splice. Would the algorithm produce the same output if we would use it?
It would have been possible by changing the lines: $left=array_slice($inputArray, 0, $middle);
$right=array_slice($inputArray, $middle);
into: $left=array_splice($inputArray, 0, $middle);
$right=$inputArray; So, if we are no longer concerned with printing out the internal steps, the function that splices could look like:


Or, making the whole a bit more synthetic, the function could also be shortened into a formally niftier:


The example(s) above fragments an input array using no additional space because it employs the mentioned array_splice, but performs no manipulation on the generated halves, so it is basically pointless: yet, one could insert in it one's own manipulations.
It also uses as argument a pointer to the original array (php, unlike javascript, allows explicit pointers): thus the original array will be affected, and at the end of that run shall hold (rightly, though uselessly) one last entry only (its rightmost original entry).

With the mergesort implementation of such divide and conquer approach, it seems that unfortunately it won't be that easy to save additional space, for the conquer part will need it. However, I thought you may like to have a snippet of Php code that halves saving space.

The difference of a mergesort divide and conquer from the example provided above, which for illustration purposes had to obey to an additional necessity to print out results that a mergesort obviously would need not to print, is that the traditional implementation of the mergesort shall recur transmitting to its recursive calls not the slices of the array itself, but firstly the mere indexes that locate such slices, and later manipulating the slices entries (in order to rearrange them in order) locating them via such indexes: function mergesort(&$inputArray, $begin, $end){
if($begin < $end){ /* if this condition holds false, NO recursion */
$middleIndex=floor( ($begin+$end)/2 ); /* floor rounds to lower */
/* DOUBLE RECURSION: */
mergesort($inputArray, $begin, $middleIndex);
mergesort($inputArray, $middleIndex+1, $end);
/* HERE SHOULD BE ADDED DATA MANIPULATION:
COMPARE FRAGMENTS EDGES, MOVE THEM IF NECCESSARY, MERGE ORDERED FRAGMENTS */
};
} That function arguments imply that to set off the function call, you pass as first argument &$inputArray the incoming array to be sorted, and as second argument $begin number zero, and as last argument $end the size of the incoming array less 1.

In fact, as number representing indexes, those numbers (zero and size-1) detect the original edges of the array before it undergoes halving. The algorithm will then take care of itself updating these values so to fit gradually shrinking halves extracted from this incoming array and passing these new values correctly to its subsequent internal recursions.

Note also that the exit condition is traditionally set as: if($begin < $end){ /* enter recursion */
//blah blah and recursion inside the conditional
} namely whatever does not fall within it, triggers no recursion and thus halts the process.

Yet, if recursion can be entered as long as the lower edge index of the current fragment is still inferior to its correlated fragment highest index, it would have been possible also setting the exit condition a bit more expressly or straightforwardly (though till now I never saw it done), namely as follows: if($begin >= $end){return;/* exit recursion */}
//blah blah and recursion outside the conditional In both cases, the variable $begin does becomes equal to $end at a certain point: but it will do so one step before the exit condition detects it did: the exit condition will find out that $begin does has attained the value of $end only at the next round, and then shall exit: that is, before the function exits, note that $begin will become identical to $end, which is exactly the case of the unary array whose leftmost edge index coincides with its rightmost one.

So, we have produced functions that halve, and we have fed them with physical arrays as arguments.
But as just noted, we could devise the function in a more completely abstract way: namely in such a way that rather than halving the array, it returns the index offsets numbers only (that is, where each new fragment would be just a numerical abstraction that begins and ends via numerical indexes only), rather than splintering the actual arrays. It would be like producing a map of the fragments, rather than the actual fragments:


Given the two options available to a divide and conquer namely to divide the actual array and pile up in the recursion its actual fragments, or to pile up in the recursion just the indexes of the portions of the array, the traditional mergesort chooses the second option.
There is a reason for this, actually.
It is that sorting algorithms should be «in place», namely they must preferably order the incoming array allowing on it as its only allowed manipulation the swaps among its entries as the ordering process goes on.
If so, fragmenting it into splinters too would violate such principle.
Of course, it is possible to produce both codes that respect or neglect this aspect, and all of them would eventually produce a sorted array, although at times as a copy.
Since the traditional mergesort doesn't want to do onto the incoming array more than swaps, its canonical versions will all use recursions meant to pile maps of indexes rather than physical fragments.

On an actual array you'd invoke the last produced function divide passing as arguments zero and the size less 1 of the meant array.
In an array of say 12 entries, that recursion would produce a map of indexes in this sequence (which I think you should understand: they clearly detect beginning and ending offsets of halves):
It is Robert Sedgewick in his books about algorithms who made the right move: he explains how to merge two ordered arrays before explaining how mergesort uses this feature. This is the correct approach, that too many other books neglect: in fact what we should wonder is: how can we merge between themselves two arrays that are already ordered?
Sedgewick's answer is very simple.

I can help you even more to understand that answer.
What is the simplest ordered array you can imagine? I guess it could be the one entry array: in fact, when an array is composed by one entry only, it can also be paradoxically thought as ordered already. With a one entry only array, order is presumed to reign, because no house that houses one guest only can be divided against itself.

So the simplest case of merging of two ordered arrays, is even simpler than the one provided by Sedgewick: it boils down to the case of two arrays of one entry each.
This means that the basic question we are trying to answer is: how do you arrange (merge) in a third bigger array two incoming arrays of one entry each (say: [8], [3]), making sure that in the new eventual array such entries are listed in order too (namely: [3, 8])?

You compare them, and you move them onto the outcome array starting with the one resulted as smaller after the comparison, sure thing.
We shall promptly see the code for this, but note since now that this is precisely the case of a divide process as described earlier in a divide and conquer approach when it has reached, halving after halving, its ultimate threshold of yielding arrays composed of one entry only.

A small PHP function that would do that might look like the following (which I shall explain soon after its code):


You might invoke it assigning the returned result to a variable: $foo = merger($ordered_array_1, $ordered_array_2);

print_r($foo); //see the ordered merged array Here it is line by line what the code above does:

• $output=array():
  initializes the output array upon which the two merged arrays shall appear.
  The function presumes that the two argument arrays are not only already sorted, but that they have been sorted in the traditional way, namely increasingly: the smaller values at the lowest array indexes, the highest values at the highest array indexes.
  
  It is possible to arrange different merger for the opposite case, namely for incoming arrays that have been sorted in decreasing order.
  It is by the way rather surprising how many application presume that sorted arrays should always be sorted in an increasing order. I never presumed this, and in fact for instance my binary searches algorithm can accommodate both cases.
• while(sizeof($array1) && sizeof($array2)){:
  we shall loop the arrays and compare their entries.
  Whenever the last entry on an array is bigger than the last entry in the other array, we shall remove such last entry and place it unto the output array. This means that over time, sooner or later, either of the two incoming arrays shall attain a length of zero because all its entries have been moved onto the output array.
  When this happen onto whichever of the incoming array, the loop will stop.
• $output[]= ( $array1[sizeof($array1)-1] > $array2[sizeof($array2)-1] )? array_pop($array1):array_pop($array2):
  This is precisely the check and removal of the biggest elements, as described in the previous point.
• while(sizeof($array1)){array_push($output, array_pop($array1));}
while(sizeof($array2)){array_push($output, array_pop($array2));}:
  Once exited the main loop, it is still possible that either of the two arrays holds some items. This happens if the two incoming arrays were of different length, because in such case one gets emptied before the other.
  This case is no specificity of my code, you shall find it dealt with also in the C mergesort of the Institut fur Medieninformatik und Technische Informatik:

  // Efficient variant
void merge(int lo, int m, int hi)
{
int i, j, k;

i=0; j=lo;
// copy first half of array a to auxiliary array b
while (j<=m)
b[i++]=a[j++];

i=0; k=lo;
// copy back next-greatest element at each time
while (k<j && j<=hi)
if (b[i]<=a[j])
a[k++]=b[i++];
else
a[k++]=a[j++];

// copy back remaining elements of first half (if any)
while (k<j)
a[k++]=b[i++];
}

  These remains, since we presumed the arrays as already sorted, are already ordered too.
  Thus, it is sufficient to append them sequentially to the output array without any further check: only one of those two ending while loops will be actually triggered, because only one of the two incoming array could be still populated.
  Besides, we know the incoming arrays are already ordered (this was out precondition, remember?), and we know that we already put all the smaller elements upon the output; therefore, these remains are necessarily both bigger and already ordered: they could be appended safely, it seems.
  
  It would have been possible using the PHP function array_merge for appending these last remains. Yet I chose not to use it because array_merge in Php generates copies, and I just wanted to eliminate as much as possible whatever chance of letting copies cluster extra disk space.

Be warned, there is something very characteristic in this snippet of mine: it takes in arrays sorted in increasing order, and it returns a merged output sorted in decreasing order. Why?
In that example I have tried to avoid as much as possible using methods like shift and unshift: such methods insert (unshift) or remove (shift) elements from an array at its lower index (zero), and thus whenever an element is added or removed via them, all the subsequent elements of the array must be reindexed. The hypothesis was that shifting and unshifting might take a bit longer as a consequence of the reindexing performed in the background.
Instead I used the complementary methods of shift and unshift which are named respectively pop and push.
These latter insert (push) and remove (pop) from the topmost edge of the array, thus requiring no reindexing because the index of an appended (=postfixed) element does not need reindexing the previous ones, but the index assigned to a prefixed element does requires reindexing the subsequent ones.
The hope is, in case of very big arrays, to save a bit of time.
Yet, exploiting this feature, meant to have an output still ordered, and yet in reversed line.

A version that, from incoming arrays ordered as increasing, would produce an output increasing as well, and thus shall make use of shifting and unshifting, is this:


A few benchmarking tests I have made, though, prove both versions taking about the same amount of time (surprisingly, the shifting process even seems to take a little bit faster), thus feel free to consider them as subtantially equivalent, whereas in such case the latter is to be preferred because it produces the traditional increasing order in the output array rather than the decreasing order yielded by the former version.

If you are wondering how it would look like a merger in that line and that accepts as incoming arrays arrays that are in decreasing order and that produces an output in decreasing order as well, it would look like this:


If you are wondering how it would look like a merger in that line and that accepts incoming arrays that are in decreasing order and that produces an output in increasing order, it would look like this:


Whichever procedure one may choose, it has to be observed that if the incoming array are both of one entry only, the output shall be an array of two entries, and ordered.

NOTE:
All those snippets return such output, which therefore in order to be used needs to be saved in some external variable, or once finished the runtime of the function, its toiled for output would simply vanish, leaving you with only the two argument arrays depopulated by the popping and shifting processes.

Now, since the divide and conquer halving process explained before ends up yielding exactly such unary arrays, lined up as extreme offsprings of all the halving processes involved in the previously explained recursion, whatever merging applied onto them shall produce arrays of two entries that are thus also ordered.

If each time such new couple is generated, it gets also compared with the new couple generated by merging the unary offsprings of another branch of the halving process, what you shall compare are arrays which are of two entries and both ordered by the previous merging of their unary versions: you can thus merge them into an array of four entries because they are fit - that is, they have the prerequisite we wanted for a merging, namely that both he incoming arrays, regardless of their lengths, are already ordered.
You can now compare this four entries array with the other four entries arrays released by the halving process and rebuilt by the merging, so to get a wider ordered array of eight entries. And so on till one final single array (as long as the original one) is generated - and ordered.

We still need to specify several things, but if now you have encompassed with clarity the conceptual puzzle, you have also understood why a mergesort works, and we can take leave of this chapter.

Let's summarize what we have ascertained thus far in a mergesort divide and conquer:

• The incoming array gets divided in gradually smaller and smaller fragments.
• This division in a mergesort is performed passing the array coordinates (map of indexes) of such fragments, not producing the actual physical fragments.
• Here the division part ends.
  Now the conquer part takes over the fragment coordinates:
• The fragments get passed to a merger, which shall:
  • Order each fragment entries.
  • Merge each ordered fragment with the other fragments of the same size already ordered at that stage, so to produce gradually bigger & ordered fragments.

Let's consider as our example incoming array the following image:


The incoming array [14, 31, 25, 4, 74, 32, 66, 7] gets divided into halved fragments.
The function that divides the array is recursive.
When such array is attacked by a divide and conquer algorithm, will call in the merging process only when the last elements produced by the first halving are met: namely when [14] and [31] are relinquished.
These get correctly ordered by the merger versions seen thus far.
But then? They disappear in the void in a recursive environment!
In fact my previous mergers order them, but not only by doing so they even remove the entries from the original fragments, but then they also store these results nowhere.

Undoubtedly, the first thing we'd need to adapt our merger, is an external array upon which we can permanently save these ordered outputs.

But if such an external array has to be introduced, it also means that the arrays to be merged, in a mergesort (do not mistake merging processes and mergesort processes as identical: merging presumes an already existing order, mergesorts don't and so the latter produce first such order and then merge) must be no longer the array fragments generated by the divide and conquer process among themselves, but they must be those generated by the divide and conquer process, grabbed one by one, and this latter gradually populated external array.

Using the function named divide, therefore we have to add to its signature two more arguments, one to pass the incoming array and another to pass the name of the external array where to save the ordered fragments.

The fact in so many codes, online and in books both, you will not find these arguments passed, entirely depends upon the fact all these codes hard code the names of such arrays within the codes themselves.
Why nearly all do so is a matter of guesswork, because this subtracts flexibility from such codes, inasmuch as they will not work any longer if either or both your incoming and external array hold different names in your applications than those presumed by these codes.
Thus, passing such names as arguments reintroduces that lacking flexibility: it is not a shortcoming of my explanations, on the contrary it's obviously rather necessary a feature that too many codes seem to neglect.

So: one of such added arguments is the incoming array to be ordered, another is this external array to populate (and in this straight case it shall be up to you to be sure that, every time you run the algorithm, such external array shall be defined and shall be empty namely not already populated by any previous process).
Note that the external array argument won't be useful directly for the divide function, but it's just ferried by it in order to pass it to the merger, which is the code part that shall use it indeed and for which it is meant.

In fact, after the recursive calls that divide, we also nest in it a call to a function named conquer that represents the merger part.
This readapted code in its entirety follows below:


A possible invocation of it might look like: divide($your_input_array_here, $external, 0, sizeof($your_input_array_here)-1); The divide recursive calls will just take care of piling up in the recursion stack the updated values for $begin, $middle, $end: this is the only actual job they do.
Then, they pass such values to the conquer part, along with the two arrays arguments, whereas only this latter function conquer will actually put in use the external array argument.

Consequently, I shall explain better the inner steps of the conquer part, because the divide part just piles up coordinates and therefore the brunt is borne by the conquer part:

• while($inputItemIndex<=$middle){
$externalArray[$externalItemIndex++]=$inputArray[$inputItemIndex++]

$inputItemIndex is equal to the starting offset coordinate $begin passed by the divide process upon this recursion pile stack. It is stored independently from the starting offset because it will be updated in the loop and it must do so without altering the $begin parameter.
  
  Since all mergers need two ordered arrays to be merged, this line builds the second array (being the first the incoming one) storing it on the external array.
  Upon being stored, this fragment is not ordered yet. It will amount to an half ($inputItemIndex<=$middle) of the incoming array fragment that spans from $begin to $end for this round. Thus two arrays are now in place, the one the incoming fragment, the other its first half.
  
  At the end of that loop, $inputItemIndex is now equal to $middle.
  
  Why such a copy of the first half is being produced, will be shown promptly.
• while($fromBeginningIndex<$inputItemIndex && $inputItemIndex<=$end)
  
  This loop is using two variables:
  $fromBeginningIndex
$inputItemIndex
  
  Since the condition for $fromBeginningIndex is set to go on as long as it is inferior to $inputItemIndex and this latter was set by the step above as equal to $middle, it means this part of the loop is scanning the first half of the incoming fragment.
  On the contrary, since the condition for $inputItemIndex is set to go on as long as it is inferior to the $end parameter and $inputItemIndex is still equal to $middle, it means this part of the loop is scanning the second half of the incoming fragment.
  
  As you may notice and as said, the incoming array is not really split in fragments, but only its coordinates are used to derive an emulation of what such fragments would have been, based upon the map coordinates currently passed, at this stage of the recursion.
  
  Checking for two conditions in this loop is necessary because it is possible that the two scanned halves have not the same length: in fact, in case of odd numbers, the length of one half is necessarily greater by one unit than the length of the other half:
  
  halves out of 4 = [1,1] + [1,1] and they are identical, being both halves composed of two entries.
  But:
  halves out of 7 = [1,1,1] + [1,1,1,1]
  
  In such case one of the established conditions might terminate before the other: if it does, also the other must stop (&&), or one of them would start indexing entries that do not exist in its own half.
  This might of course determine remains left in the fragment, which are dealt with by the last loop in the function.
  
  Since in the divide function the middle points of the fragments get calculated via the following expression (by the way, equivalent to casting the result into an integer):
  
  $middle=floor(($begin+$end)/2);
  
  it means that the middle point, in case of an odd result of the division by 2, is rounded to the lower nearest unit (floor).
  
  And since the first loop within the conquer code predicates, as seen, that:
  
  while($inputItemIndex<=$middle){
$externalArray[$externalItemIndex++]=$inputArray[$inputItemIndex++]
  
  it derives (or so it seems to my reasoning, and I could be wrong about this) that it is only the external array fragment coordinates that might yield, for odd numbers, the shorter fragment because it is such fragment the first one that is created based upon the result of a rounding by floor of its rightmost edge.
• if($externalArray[$externalItemIndex]<=$inputArray[$inputItemIndex]){
  
  This check starts the ordering process.
  In the emulation setting that pretends to have two actual fragments by deriving them out of the coordinates, the check verifies whether the first item in the first half (having been such half copied onto the external array) of the fragment (stored in the external array) is inferior to the first item in the second half (being such half still left onto the original array, and detected there in place via indexes).
  If you have read above, this should sound familiar to you: it is exactly like what a merger does between two arrays.
  
  If this check returns true what happens is:
  
  
  $inputArray[$fromBeginningIndex++] = $externalArray[$externalItemIndex++];}
  
  If it doesn't:
  
  
  else{$inputArray[$fromBeginningIndex++] = $inputArray[$inputItemIndex++];}
  
  As you may notice in both cases foreseen by the conditional checks the consequence is that the inputArray is updated (=gets ordered).
  
  It is because of this update, that the use of an external array can be definitely accounted for.
  If no such external array would be present, there would be no stable comparison criterion between an anterior and a new status because the original undergoes changes that must be determined by contrast with a permament image (at least for each recursion round) of how the situation was anterior to the changes.
  Thus the external array acts like sort of a biological RNA that leaves the nucleus of the cell (array) to provide a photographic film for its own DNA helping its replication (or better, in our case: rearrangement) by providing a track guide of the original status while it synthesizes changes in the original array:
  One of the main functions of RNA is to copy genetic information from DNA (via transcription) and then translate it into proteins (by translation).
  (...) Structurally, RNA is indistinguishable from DNA.
  (...) Once mRNA has been transcribed from DNA, it is exported from the nucleus into the cytoplasm.
  
  [source]
  To avoid misunderstandings, the excerpt above does not attempt to imply that biology imitates artificial intelligence, and that living beings are successful machines: if it implies something, it may rather mean that artificial intelligence imitates biology, and that machines unsuccessfully strive to reproduce living beings. Because biological life was born before me, you, and John von Neumann too.
  
  The swappings that are performed within the conditional checks are so sophisticated in order to keep the procedure as «in place», that I really have no idea how long it took to von Neumann to fine tune them. In the original array continuously coexist both halves, the one undergoing changes and the one still unaffected as per the coordinates of each recursion.
  In fact, since the algorithm wants to be «in place», consequently both the checks end up updating the input array $inputArray.
  
  The first conditional check, namely as already seen:
  
  
  if($externalArray[$externalItemIndex] <= $inputArray[$inputItemIndex]){
$inputArray[$fromBeginningIndex++] = $externalArray[$externalItemIndex++];}
  
  draws the update from the copy $externalArray which latter is storing the first half of the input array itself namely from its beginning till the current $middle coordinate as passed from the divide and conquer process.
  
  Instead the second check, namely as already seen:
  
  
  else{$inputArray[$fromBeginningIndex++] = $inputArray[$inputItemIndex++];}
  
  draws it from the second half of the input array itself because the used index namely $inputItemIndex starts from the middle because it was updated upon creating the copy into $externalArray by the previous code portion that went, as already seen:
  
  while($inputItemIndex <= $middle){$externalArray[$externalItemIndex++] = $inputArray[$inputItemIndex++];}
  
  Note the ++ part.
  
  Note also that in the other while loop (the merger), namely as already seen:
  
  while($fromBeginningIndex < $inputItemIndex && $inputItemIndex <= $end){

$inputItemIndex does not scan the second half of the array till the very end of the array itself but only till the end as passed by the divide process via the variable named $end, which actually stands for the current end in the current second half coordinates (it was meant as the real utmost end of the array only when starting the divide process).
  
  Each time this sophisticated setting enters a new recursion, it finds an input array to work on that has been renewed and updated (=has been more ordered) by each previous recursive rounds.
  
  I would dare call this "easy" (as alleged newsgroup experts enjoy saying while posing for the photo) by no accounts, ever!
  
  If you go on groups like javascript and the alike on Google or Usenet, you will find plenty of these experts, lecturing everybody like utter morons, who understand nothing and yet read everything. They read ECMA script specifications, and feel they do not need explanations, because it is written and thus done deal. Maybe at school they have been taught to learn mathematical formulas by heart, with no demonstration about the whys and the whereofs, and thus think that the latter are not needed.
  Why should you wish you could understand, when you can just repeat as an empty drum? They call this with this name: «strong commitment to spread publicly good programming practice».
  
  I have created a file with printed down a few of the results as the function conquer goes on: click here for it.

Of course, the most convenient way to encapsulate as much as possible external variables, so to pass to the function one argument only namely only the input array to be sorted, is to rearrange the code above as a class:


With the class code above, all you have to sort an incoming array is to initialize a variable (placeholder name for the example is $foo): $foo = new mergesort($your_input_array_here);
//or even just:
new mergesort($your_input_array_here); That class is ultrafast: sorts an array of 100,000 shuffled entries in 6 seconds on my pentium 2000+. For 1000 entries it takes 1/200 of a second.
The array passed as argument will result sorted, and you need to assign only it as its only argument, for the class will take care of elaborating all the other needed arguments, thus also without letting them tamper with the global scope.
Ah, the joys of class encapsulation!

As for a non recursive version of a mergesort, I partially reproduce here, of course rearranged as a PHP code, the Perl version that Orwant, Hietaniemi & Macdonald propose in their book Mastering Algorithms With Perl.

The particular idea it borrows from that book is that it emulates the fragmentation of the incoming array as the authors suggest: by nesting the sorting and merging loop within an external loop where there is a variable that is increased by multiples of 2 at each iteration so to simulate the growing halved fragments.
Yet the merging engine I use in there is no longer the one provided by Orwant, Hietaniemi & Macdonald but the one I used in the previous examples.

However, in Orwant, Hietaniemi & Macdonald codes (at least in the first edition of their good book, which I think is still the current one on year 2005) there was what seems to be an error. The function exhibited a flaw, namely firstly it returned erroneous results, moreover such results even changed upon subsequent tests (additionally featuring the very insidious characteristic that occasionally they were the right ones!) although invariably tested with the same input array.

Then, when I tried a few fixes to try see whether I could locate in which part of the code the error might be loitering (rain dance is not to be recommended, but it can be very good to shrink the areas responsible in a code for undesired or unexpected behaviours), it sorted right but appended empty entries on top of the sorted array.
Whichever merging engine you used (theirs or the one I used before), the error persisted: therefore it wasn't in the merging part.

Being the error still the same also using different mergers, it became apparent to my eyes that the error had to be located in the earliest loops outside the merger.
I reported this possible issue.

Of course I tried to include a fix, which arguably had to do with the parameter named $end and $middle: in fact, upon printing them, they at times weren't the expected ones, spanning beyond the fragments boundaries.
The only solution I found out was to replace in the Orwant, Hietaniemi & Macdonald code the line that checks:
$end=($end<$length)?$end:$lastIndex;
with these two checks: if($end>=$length){ $end=$lastIndex;/*also moving before $middle did not resolve the flaw*/ };
if($middle>$end){ $middle=$end; }; Their original code did not include the lines I report as I report them (besides using quite different a merger, but it is immaterial for we saw the problem could not stay with the merger), for I changed the variable names to something more user friendly in my humble opinion. If you want a look at the original code, and verify whether I may have misunderstood something (feel free to email me if you think I did), here it is (comments are mine):
As for my PHP function version, rearranged as mentioned before the Perl digression, the code is below:
You just have to call in the function passing to it one argument only, like in the class version; namely you simply have to pass as argument the incoming array: unrecursive_mergesort($your_input_array_here);
/*$your_input_array_here is now sorted array*/ If moreover you want a mergesort that has an advantage and a setback, whereas the advantage is that it does not use extra space (it does not operate in place, that is), and whereas the setback is that it is much slower than the canonical version (at least if you start using arrays above 5000 entries, whereas otherwise it could be an acceptable alternative, still reasonably fast enough, for not too long arrays that anyway hold sizeable elements whose copies produced by an «in place» mergesort might cause problems), I have devised the following experimental and yet working mergesort:
It does not order the input array, which at the end of the run will be emptied. It rather returns a brand new ordered array housing the elements present in what was the incoming array. So, store the returned result in some variable of your choice: $foo = mergesort_notinplace($your_input_array_here); /*$foo is now the sorted array*/