Ytl's Java Blog

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Algorithm to merge sorte

Posted on 2011-05-06 17:05 ytl 阅读(275) 评论(0)  编辑  收藏 所属分类: Algorithms and programming concepts
Merge sort is an O(n log ncomparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm. Merge sort was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up mergesort appeared in a report byGoldstine and Neumann as early as 1948
 divide and conquer algorithm: 1, split the problem into several subproblem of the same type. 2,solove independetly. 3 combine those solutions

Python Implement
  def mergeSort(L):
         if len(L) < 2 :
               return  L
         middle = len(L)/2
         left = mergeSort(L[:mddle])
         right = mergeSort(L[middle:])
         together = merge(left,right)
         return together