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.