License Creative Commons Attribution Share Alike 3.0-US
Keywords
divide and conquer (2)
Permissions
Viewable by Everyone
Editable by All Siafoo Users
Hide
Bored? Check out the Recent Activity on Siafoo 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++