Shuffle and sort for mapreduce

Question

I read through the definitive guide and some other links on the web including the one here

My question is

where exactly does shuffling and sorting happen?

As per my understanding, they happen on both mappers and reducers. But some links mention that shuffling happens on mappers and sorting on reducers.

Can someone confirm if my understanding is correct; if not can they provide additional documentation I can go through?

Answer 1

Shuffle:

MapReduce makes the guarantee that the input to every reducer is sorted by key. The process by which the system performs the sort and transfers map outputs to the reducers as inputs is known as the shuffle.

Sort:

Sorting happens in various stages of MapReduce program, So can exists in Map and Reduce phases.

Please have a look at this diagram

Adding more description to above image in Map and Reduce phases.

The Map Side:

When the map function starts producing output, it is not simply written to disk. Before Map output writes to disk, the thread first divides the data into partitions corresponding to the reducers that they will ultimately be sent to. Within each partition, the background thread performs an in-memory sort by key.

The Reduce Side:

When all the map outputs have been copied, the reduce task moves into the sort phase (which should properly be called the merge phase, as the sorting was carried out on the map side), which merges the map outputs, maintaining their sort ordering. This will be done in rounds.

Source : Hadoop Definitive Guide.