合併排序創建堆棧溢出

Question

我不明白爲什麼這種合併排序導致堆棧溢出。是因爲我沒有基礎案例，如果是的話，我會如何去添加它？對於像我這樣的初學者來說，合併排序是相當先進的:(所以我會很感激任何幫助或建議 此外，我一直無法理解數據存儲在哪裏，一旦你遞歸地分割數組我知道分裂原始數組會破壞它分解成單個的元素，但如果是這些單個元素存儲??

Sub Main() 
    Dim Array() As Integer = {5, 4, 3, 1, 2, 6} 
    Dim right As Integer = Array.Length - 1 'find right index 
    Dim left As Integer = 0 'set left index 
    mergeSort(Array, left, right) 
End Sub 

Sub mergeSort(Array, left, right) 
    Dim middle As Integer 
    If left < right Then 
     middle = (left + right)/2 

     'recursively split both halves of the array 
     mergeSort(Array, left, middle) 
     mergeSort(Array, middle + 1, right) 

     'sort individual elements 
     mergeSortedArray(Array, left, middle, middle + 1, right) 
    End If 
End Sub 

Sub mergeSortedArray(ByRef Array, left, middle, rbeg, right) 
    Dim pt As Integer = 0 
    Dim TempArray(6) 

    While (left <= middle) And (rbeg <= right) 'sort every element 
     If Array(left) < Array(rbeg) Then 
      TempArray(pt) = Array(left) 
      left += 1 
     Else 
      TempArray(pt) = Array(rbeg) 
      rbeg += 1 
     End If 
     pt += 1 
    End While 

    If left > middle Then 
     While rbeg <= right 'left sub array exhausted 
      TempArray(pt) = Array(rbeg) 
      rbeg += 1 
      pt += 1 
     End While 
    Else 
     While left <= middle 'right sub array exhausted 
      TempArray(pt) = Array(left) 
      left += 1 
      pt += 1 
     End While 
    End If 

    For Each element In TempArray 
     Console.WriteLine(element & " ") 
    Next 
End Sub 

Answer 1

很多問題與此代碼在VB合併排序會看起來更像是這樣：

Sub Main() 
    Dim Array() As Integer = {5, 33, 3, 10, 2} 'make the array 

    'Split Array: you need the leftmost index & rightmost index 
    Split(Array, 0, 4) 
    Console.ReadKey() 

End Sub 

Sub Split(Array, left, right) 
    If left < right Then 'if the array has elements.. 
     Dim middle As Integer = (left + right) \ 2 'find halfway point 

     Split(Array, left, middle) 'split left array 

     Split(Array, middle + 1, right) 'split right array 
     'recursion keeps on splitting the two arrays until we have a bunch of single elements 

     'now sort and merge 
     Merge(Array, left, middle, right) 
    End If 
End Sub 
Sub Merge(ByRef Array, left, middle, right) 

    Dim SizeA As Integer = middle - left + 1 
    Dim SizeB As Integer = right - middle 
    Dim LeftArray(SizeA) As Integer 'set size of left array. 
    Dim RightArray(SizeB) As Integer 'set size of right array 

    'Left & Right pointers to keep track of what elements in the array we are referring to 
    Dim LP As Integer 
    Dim RP As Integer 

    For LP = 0 To SizeA - 1 
     LeftArray(LP) = Array(left + LP) 'assign 0 index of original array to left hand array (5) 
    Next 

    For RP = 0 To SizeB - 1 
     RightArray(RP) = Array(middle + 1 + RP) 'assign 1 index of original array to right hand array (33) 
    Next 

    'reset pointers 
    LP = 0 
    RP = 0 
    Dim i = left 'set a pointer for the original array 

    'swap elements if need be: 
    While LP < SizeA And RP < SizeB 
     If LeftArray(LP) <= RightArray(RP) Then 'if element in left array is smaller that the one in the right 
      Array(i) = LeftArray(LP) 'assign the left value to the original array 
      LP += 1 ' increment the left array's pointer 
     Else 
      Array(i) = RightArray(RP) 'otherwise the original array gets the right element 
      RP += 1 'increment the right array's pointer 
     End If 
     i += 1 'now increment the counter for our new array 
    End While 

    'Hang on...what if there are still elements in the left array 
    While LP < SizeA 
     Array(i) = LeftArray(LP) 'assign these elements to the new array 
     LP += 1 'increment the left pointer 
     i += 1 'increment the new array's pointer 
    End While 

    'Hang on...what if there are still elements in the right array 
    While RP < SizeB 
     Array(i) = RightArray(RP) 'assign these elements to the new array 
     RP += 1 'increment the right pointer 
     i += 1 'increment the new array's pointer 
    End While 

    'write out the new array 
    For Each element In Array 
     Console.Write(element & " ") 
    Next 
    Console.WriteLine("") 
    'start the second pass 
End Sub