Javascript algorithm – Merge sort簡介與實踐

tags: wordpress algorithm

前言

排序是程式語言中必然繞不過的項目之一，你可能不知道排序的原理是什麼，但你一定用過sort! 實際上各種程式語言中的sort也是經由不同的排序演算法來實踐的，今天就來介紹一下一個有名的排序演算法Merge sort!

Merge sort核心概念

merge sort是基於Divide and Conquer的概念而實踐的一種排序方式， 而Divide and Conquer包含著以下的步驟

1. 將原先的問題打散為較小的問題
2. 一一解決被打散的小問題
3. 將你攻克小問題得到的解答合併為原先問題的解答

也就是說，實際上Merge sort是藉由不斷的將陣列打散為小塊(sublist)直到每個小塊都僅剩一個元素後，接著再按希望的方式結合這些小塊，最終得到一個排序後的陣列。

大體上可以拆成兩個函數來實現merge sort，每個函數內該做的事情如下

function mergesort(array) {

1. 檢查該陣列是否能被繼續打散
2. 找出中間的位置(從中間打散陣列)
3. 將原本的陣列拆為兩個sublist
4. 利用遞迴持續以上的操作，直到陣列只剩一個元素 }

function merge(left, right) {

1. 建立一個新陣列
2. 檢查左右兩陣列是否有空陣列 若兩者皆不是空陣列，則比較兩陣列內的元素 將較小的元素推進新陣列
3. 合併左陣列、右陣列
4. 回傳新陣列 }

以程式碼實踐的結果會是如以下

function mergeSort(array) {
  // 檢查該陣列是否能被繼續打散
  if (array.length < 2) return array

  // 找出中間的位置(從中間打散陣列)
  const middleIndex = Math.floor(array.length/2)

  // 將原本的陣列拆為兩個sublist
  const leftSide = array.slice(0, middleIndex)
  const rightSide = array.slice(middleIndex)

  // 利用遞迴持續以上的操作，直到陣列只剩一個元素，接著利用merge將小陣列組為一個排序後較大的陣列
  console.log('切割的結果為:', leftSide, rightSide)
  return merge(mergeSort(leftSide), mergeSort(rightSide))
}

function merge(left, right) {
  // 建立一個新陣列
  const result = []
  
  // 檢查左右兩陣列是否都不為空陣列
  while (left.length && right.length) {
    // 將較小的元素推進新陣列，同時將該元素從原本的陣列抽離
    left[0] <= right[0] ? result.push(left.shift()) : result.push(right.shift())
  }

  // 合併左陣列(若左陣列還有元素，則將該元素推進result))
  while (left.length) result.push(left.shift())

  // 合併右陣列
  while (right.length) result.push(right.shift())

  // 回傳新陣列
  console.log('回傳的結果為', result)
  return result
}

mergeSort([1,2,3,5,8,-5,-3,2]) // [-5, -3, 1, 2, 2, 3, 5, 8]

在程式碼中我加入了每次遞迴時的內容，實際印出東西會讓人更容易理解發生了什麼事情! 總之每一次都會先將陣列打散到只剩一個元素，將這些小陣列丟進merge函數中結合並排序後，再與同樣處理好的陣列結合併排序，最終得到一個排序後的陣列!

這樣的排序方式在時空間複雜度的表現為(原因請參照參考文章)

• Time complexity: O(n logn)
• Space complexitt: O(n) (需要一個與原陣列長度相同的空間)

結語

排序的演算法其實非常多種，常見的就有quick sort、tim sort、binary sort等等等，之前其實都略有接觸，但從來沒有仔細的細究它們的原理，這次因為要研究linked list的題目才讓我決定好好的內化一下這樣的知識，之後應該會針對quick sort & binary sort也都寫一篇記錄~! 希望這樣的文章多少也有幫助到想理解這個演算法的人囉:D

參考資料

合併排序 (Merge Sort)

Merge Sort Algorithm