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.