Merge sort effectively breaks your unsorted list into smaller unsorted lists, sorts the smaller ones, then merges the lists together. This algorithm actually uses recursion to be effective.
http://www.sorting-algorithms.com
- If the list has more than 1 element, split it in two halves and run merge sort on each half.
- Merge the two halves back together: as long as their are still items in one of the lists…
- Compare the first element of each list.
- Add whichever is first to your output list and remove it from the sub-list.