merge sort

merge sort

1. how it works

   • uses a technique called divide and conquer
   • The list is repeatedly divided into two until all the elements are separated individually.
   • Pairs of elements are then compared, placed into order and combined.

2. example

   • 1 21 3 4 0 10 8 9
     • 1 21 3 4
       • 1 21
         • 1
           • 1 21
             • 1 3 4 21
               • 0 1 3 4 8 9 10 21
         • 21
       • 3 4
         • 3
         • 4
           • 3 4
     • 0 10 8 9
       • 8 9
         • 8
           • 8 9
         • 9
       • 0 10
         • 0
           • 0 10
             • 0 8 9 10
         • 10

3. The pairs are then compared, starting with the first number in each pair >

   • < If the left hand number is smaller than the right hand number, it is placed in order.