“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Algorithm thought

Merge sort is a stable sort, is the application of the idea of divide and conquer, divide is to first divide the problem into small problems, conquer is to merge the answers of the various problems in stages

Images from www.cnblogs.com/chengxiao/p…

The process of grading

I’m going to deal with the left and right

Conclusion thought

  • I’m going to do the left-hand side, and I’m going to get the left-hand side
  • I’ll do it on the right, and I’ll get the information on the right
  • And then finally, we’re dealing with information across both sides

Code demo

var mergeSort = function (sum, l, r) {
  if (l >= r) return
  var mid = Math.floor((l + r) / 2) / / midpoint

  mergeSort(sum, l, mid) // Recurse to the left
  mergeSort(sum, mid + 1, r) // Recurse to the right
  // Become an ordered array

  var temp = new Array(r - l + 1) // With storage space

  var k = l,
    p1 = l,
    p2 = mid + 1
  // Add smaller values to temp
  while (p1 <= mid || p2 <= r) {
    if (p2 > r || (p1 <= mid && sum[p1] <= sum[p2])) {
      temp[k++] = sum[p1++]
    } else {
      temp[k++] = sum[p2++]
    }
  }
  for (var i = l; i <= r; i++) sum[i] = temp[i] // Copy the storage space back to the original array
  return
}

var arr = [8.1.5.6.3.2.7.4.9]

mergeSort(arr, 0, arr.length - 1)
console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
Copy the code

Merge sort can solve the problem

148. Sort linked lists

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var sortList = function (head) {
  var count = 0 // List length
  var p = head
  while (p) {
    p = p.next
    count++
  }
  return mergeSort(head, count)
};
// merge sort
var mergeSort = function (head, n) {
  if (n <= 1) return head
  var left_cnt = n >> 1.// The left and right list lengths
    right_cnt = n - left_cnt
  var l = head,/ / the left list
    r = l,/ / right list
    p = l,
    ret = new ListNode()// Virtual header pointing to the list to be returned
  for (var i = 1; i < left_cnt; i++) {
    p = p.next
  }
  r = p.next
  p.next = null// Break the linked list
  // Sort the list recursively
  l = mergeSort(l, left_cnt)
  r = mergeSort(r, right_cnt)
  p = ret
  while(l || r) {
    if(r == null || (l && l.val <= r.val)){
      // Point the virtual header to the smaller list
      p.next = l;
      p = l;
      l = l.next;
    }else{
      p.next = r;
      p = r;
      r = r.next
    }
  }
  
  return ret.next
}
Copy the code

To be continued