notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

MergeSort.md (887B)

      1 # Merge Sort
      2 
      3 CLRS 2.3
      4 
      5 **Definition:** Merge sort is an algoritmh that uses [DivideAndConquer](DivideAndConquer.md) to sort a list in log linear (n log(n)) time.
      6 
      7 Sample Implementation:
      8 
      9 ```python3
     10 
     11 def merge(ls):
     12 
     13     # Base case length of 1
     14     if len(ls) == 1:
     15         return ls
     16     
     17     # Split list in half
     18     pivot = int(len(ls) / 2)
     19     left = ls[0 : pivot]
     20     right = ls[pivot :]
     21 
     22     # Recurse
     23     left = merge(left)
     24     right = merge(right)
     25 
     26     leftPos = 0
     27     rightPos = 0
     28     sorted = []
     29 
     30     # Merge lists (O(n))
     31     while leftPos < len(left) and rightPos < len(right):
     32         if left[left Pos] < right[right Pos]:
     33             sorted.append(left[left Pos])
     34             leftPos += 1
     35         else:
     36             sorted.append(right[right Pos])
     37             rightPos += 1
     38     
     39     sorted.extend(left[leftPos:])
     40     sorted.extend(right[rightPos:])
     41     
     42     return sorted
     43 
     44 ```