Merge Sort is a divide and conquer sorting algorithm. It is much more efficent than either Bubble Sort or Insertion Sort with an average and worst case time complexity of O(n log n).
In Merge Sort, you divide a list of items to be in the smallest units possible. You sort the smaller units, then repeatedly merge the small units back together until you have a sorted list.
- Take an array of items. Split the array into single subunits.
- Since an item with only one input is considered sorted, merge the subunits together so that you now have subunits with 2 items each.
- Sort each of these 2-item subunits so that they are all ordered correctly.
- Continue merging the subunits together and sorting them individually until you have a completely merged and sorted list.
As discussed, Merge Sort has a very good time complexity. However, it does not have a good space complexity. Because it doesn’t sort in place (like Bubble Sort), you need twice the space of the normal list in order to implement the sort. Despite this drawback, it is still worthwhile because of its efficiency. For example, Merge Sort’s worst case time complexity O(n log n) is the same as Quicksort’s best case time complexity.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
This is the third post in a series of posts on various sorting algorithms in computer science. See the entire series here.