# Sorting Algorithms: Merge Sort

Merge sort algorithm is a comparison-based sorting algorithm. In this sample, we use top-down implementation, which recursively splits list into two halves (called sublists) until size of list is 1. Then merge these two sublists and produce a sorted list. This sample could run in serial, or in parallel with Intel® Cilk™ Plus keywords cilk_spawn and cilk_sync. For more details about merge sort algorithm and top-down implementation, please refer to http://en.wikipedia.org/wiki/Merge_sort.

#### Code Change Highlights:

• `cilk_spawn`
• serial version:
`void merge_sort(int a[], int tmp_a[], int first, int last) { if (first < last) { int middle = (first + last + 1) / 2; merge_sort(a, tmp_a, first, middle - 1); merge_sort(a, tmp_a, middle,last); merge(a, tmp_a, first, middle, last); } }`
`cilk_spawn` version:
`void merge_sort(int a[], int tmp_a[], int first, int last) { if (first < last) { int middle = (first + last + 1) / 2; cilk_spawn merge_sort(a, tmp_a, first, middle - 1); merge_sort(a, tmp_a, middle,last); cilk_sync; merge(a, tmp_a, first, middle, last); } }`

#### Performance Data:

Note: Modified Speedup shows performance speedup with respect to serial implementation.

Modified Speedup Compiler (Intel® 64) Compiler options System specifications
cilk_spawn: 4.0x Intel C++ Compiler 15.0 for Windows /O2 /Qipo /MD Microsoft Windows Server* 2012 (x64)
2rd generation Intel® Xeon® E3 1280 CPU @ 3.50GHz
8GB memory
cilk_spawn: 3.8x Intel C++ Compiler 15.0 for Linux -O2 -ipo Red Hat Enterprise Linux Server 7
3nd Generation Intel® Core™ i7-4790 CPU @ 3.60GHz
32GB memory

### Build Instructions:

• For Microsoft Visual Studio* 2010 and 2012 users:
• Open the solution `.sln` file
[Optional] To collect performance numbers (will run example 5 times and take average time):
• Project Properties -> C/C++ -> Preprocessor -> Preprocessor Definitions: add `PERF_NUM`
Choose a configuration (for best performance, choose a release configuration):
• Intel-debug and Intel-release: uses Intel® C++ compiler
• VSC-debug and VSC-release: uses Visual C++ compiler (only linear/scalar will run)
• For Windows* Command Line users:
• Enable your particular compiler environment
For Intel® C++ Compiler:
• Open the appropriate Intel C++ compiler command prompt
• Navigate to project folder
• Compile with `Build.bat [perf_num]`
• `perf_num`: collect performance numbers (will run example 5 times and take average time)
• To run: `Build.bat run [help|0|1|2|3|4]`
For Visual C++ Compiler (only linear/scalar will run):
• Open the appropriate MicrosoftVisual Studio* 2010 or 2012 command prompt
• Navigate to project folder
• To compile: `Build.bat [perf_num]`
• `perf_num`: collect performance numbers (will run example 5 times and take average time)
• To run: `Build.bat run`
• For Linux* or OS X* users:
• Set the icc environment: `source <icc-install-dir>/bin/compilervars.sh {ia32|intel64}`
Navigate to project folder
For Intel® C++ compiler:
• To compile: `make [icpc] [perf_num=1]`
• `perf_num=1:` collect performance numbers (will run example 5 times and take average time)
• To run: `make run [option=help|0|1|2|3|4]`
For gcc (only linear/scalar will run):
• Compile with `make gcc [perf_num=1]`
• `perf_num=1:` collect performance numbers (will run example 5 times and take average time)
• To run: `make run`
For more complete information about compiler optimizations, see our Optimization Notice.