License Creative Commons Attribution Share Alike 3.0-US
Keywords
divide and conquer (2)
Permissions
Viewable by Everyone
Editable by All Siafoo Users
Hide
Stay up to dateembedded code automagically updates, each snippet and article has a feed Join Siafoo Now or Learn More

Merge Sort Atom Feed 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 Log Linear
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 = 0
16 counter_2 = 0
17
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 += 1
23 else
24 array[i] = array_2[counter_2]
25 counter_2 += 1
26
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++