##### Permissions
Viewable by Everyone
Editable by All Siafoo Users
Stay up to dateembedded code automagically updates, each snippet and article has a feed

# Merge Sort 0

 In Brief Mergesort is a simple divide and conquer sorting algorithm. It works by recursively splitting an unsorted array into two sub-arrays then merging the sorted results.... more
 Performance Bound
 Implementation Difficulty
` 1 function merge_sort(array) 2      3     // Assume power of 2 array size 4     // Split using a pythonesque slice 5     array_1 = merge_sort(array[len(array) / 2 : ]) 6     array_2 = merge_sort(array[ : len(array) / 2]) 7          8     array = merge(array_1, array_2) 9 10 11 function merge(array_1, array_2)12     13     array = new_array(len(array_1) + len(array_2)) // Create new sortable array 14     15     counter_1 = 016     counter_2 = 017 18     for i → len(array)19 20         if array_1[counter_1] < array_2[counter_2]21             array[i] = array_1[counter_1]22             counter_1 += 123         else24             array[i] = array_2[counter_2]25             counter_2 += 126     27     return array`

Mergesort is a simple divide and conquer sorting algorithm. It works by recursively splitting an unsorted array into two sub-arrays then merging the sorted results.

Note that the pseudocode above assume that the length of the unsorted array is a power of two, in order to avoid dealing with sub-arrays of non-equal length.

 [Weiss1999] Mark Allen Weiss. Data Structures & Algorithm Analysis in C++