I am trying to sort this multidimensional array after the number on the first index using the merge sort algorithm, but I am very unsure on how to do so.
This is the multidimensional array I am trying to sort:
Orders_db = [[1347517405, 54413, '78'], [1347517413, 54421, '86'], [1347517454, 54462, '127'], [1347517460, 54468, '133'], [1347517461, 54469, '134'], [1347517426, 54434, '99'], [1347517464, 54472, '137'], [1347517394, 54402, '67'], [1347517445, 54453, '118'], [1347517375, 54383, '48'], [1347517377, 54385, '50'], [1347517392, 54400, '65'], [1347517450, 54458, '123'], [1347517404, 54412, '77'], [1347517389, 54397, '62'], [1347517393, 54401, '66'], [1347517440, 54448, '113'], [1347517457, 54465, '130'], [1347517444, 54452, '117'], [1347517400, 54408, '73'], [1347517412, 54420, '85'], [1347517371, 54379, '44'], [1347517415, 54423, '88'], [1347517441, 54449, '114'], [1347517435, 54443, '108'], [1347517409, 54417, '82'], [1347517398, 54406, '71'], [1347517422, 54430, '95'], [1347517468, 54476, '141'], [1347517402, 54410, '75'], [1347517437, 54445, '110'], [1347517446, 54454, '119'], [1347517382, 54390, '55'], [1347517399, 54407, '72'], [1347517438, 54446, '111'], [1347517416, 54424, '89'], [1347517380, 54388, '53'], [1347517425, 54433, '98'], [1347517406, 54414, '79'], [1347517449, 54457, '122'], [1347517388, 54396, '61'], [1347517430, 54438, '103'], [1347517455, 54463, '128'], [1347517458, 54466, '131'], [1347517452, 54460, '125'], [1347517396, 54404, '69'], [1347517423, 54431, '96'], [1347517465, 54473, '138'], [1347517397, 54405, '70'], [1347517459, 54467, '132'], [1347517395, 54403, '68'], [1347517381, 54389, '54'], [1347517424, 54432, '97'], [1347517436, 54444, '109'], [1347517434, 54442, '107'], [1347517401, 54409, '74'], [1347517376, 54384, '49'], [1347517467, 54475, '140'], [1347517456, 54464, '129'], [1347517427, 54435, '100'], [1347517383, 54391, '56'], [1347517451, 54459, '124'], [1347517433, 54441, '106'], [1347517414, 54422, '87'], [1347517417, 54425, '90'], [1347517453, 54461, '126'], [1347517378, 54386, '51'], [1347517432, 54440, '105'], [1347517403, 54411, '76'], [1347517439, 54447, '112'], [1347517448, 54456, '121'], [1347517410, 54418, '83'], [1347517391, 54399, '64'], [1347517447, 54455, '120'], [1347517421, 54429, '94'], [1347517379, 54387, '52'], [1347517411, 54419, '84'], [1347517386, 54394, '59'], [1347517384, 54392, '57'], [1347517374, 54382, '47'], [1347517462, 54470, '135'], [1347517431, 54439, '104'], [1347517419, 54427, '92'], [1347517428, 54436, '101'], [1347517466, 54474, '139'], [1347517443, 54451, '116'], [1347517463, 54471, '136'], [1347517385, 54393, '58'], [1347517387, 54395, '60'], [1347517373, 54381, '46'], [1347517372, 54380, '45'], [1347517418, 54426, '91'], [1347517420, 54428, '93'], [1347517469, 54477, '142]'], [1347517442, 54450, '115'], [1347517408, 54416, '81'], [1347517390, 54398, '63'], [1347517407, 54415, '80'], [1347517429, 54437, '102']]
And I can implement a general merge sort algorithm, but i cannot do it in a way where I sort after the number in the array on the first index.
My implementation of merge sort is:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
return arr
How can I fit the general merge sort algorithm to sort this array?
The preferred answer is that it returns the array with the highest number in the end.
Try below:
def merge(left, right):
if not len(left) or not len(right):
return left or right
result = []
i, j = 0, 0
while (len(result) < len(left) + len(right)):
if left[i][0] < right[j][0]:
result.append(left[i])
i+= 1
else:
result.append(right[j])
j+= 1
if i == len(left) or j == len(right):
result.extend(left[i:] or right[j:])
break
return result
def mergesort(list):
if len(list) < 2:
return list
middle = len(list)/2
left = mergesort(list[:middle])
right = mergesort(list[middle:])
return merge(left, right)
seq = [[1347517405, 54413, '78'], [1347517413, 54421, '86'], [1347517454, 54462, '127'], [1347517460, 54468, '133'], [1347517461, 54469, '134'], [1347517426, 54434, '99'], [1347517464, 54472, '137'], [1347517394, 54402, '67'], [1347517445, 54453, '118'], [1347517375, 54383, '48'], [1347517377, 54385, '50'], [1347517392, 54400, '65'], [1347517450, 54458, '123'], [1347517404, 54412, '77'], [1347517389, 54397, '62'], [1347517393, 54401, '66'], [1347517440, 54448, '113'], [1347517457, 54465, '130'], [1347517444, 54452, '117'], [1347517400, 54408, '73'], [1347517412, 54420, '85'], [1347517371, 54379, '44'], [1347517415, 54423, '88'], [1347517441, 54449, '114'], [1347517435, 54443, '108'], [1347517409, 54417, '82'], [1347517398, 54406, '71'], [1347517422, 54430, '95'], [1347517468, 54476, '141'], [1347517402, 54410, '75'], [1347517437, 54445, '110'], [1347517446, 54454, '119'], [1347517382, 54390, '55'], [1347517399, 54407, '72'], [1347517438, 54446, '111'], [1347517416, 54424, '89'], [1347517380, 54388, '53'], [1347517425, 54433, '98'], [1347517406, 54414, '79'], [1347517449, 54457, '122'], [1347517388, 54396, '61'], [1347517430, 54438, '103'], [1347517455, 54463, '128'], [1347517458, 54466, '131'], [1347517452, 54460, '125'], [1347517396, 54404, '69'], [1347517423, 54431, '96'], [1347517465, 54473, '138'], [1347517397, 54405, '70'], [1347517459, 54467, '132'], [1347517395, 54403, '68'], [1347517381, 54389, '54'], [1347517424, 54432, '97'], [1347517436, 54444, '109'], [1347517434, 54442, '107'], [1347517401, 54409, '74'], [1347517376, 54384, '49'], [1347517467, 54475, '140'], [1347517456, 54464, '129'], [1347517427, 54435, '100'], [1347517383, 54391, '56'], [1347517451, 54459, '124'], [1347517433, 54441, '106'], [1347517414, 54422, '87'], [1347517417, 54425, '90'], [1347517453, 54461, '126'], [1347517378, 54386, '51'], [1347517432, 54440, '105'], [1347517403, 54411, '76'], [1347517439, 54447, '112'], [1347517448, 54456, '121'], [1347517410, 54418, '83'], [1347517391, 54399, '64'], [1347517447, 54455, '120'], [1347517421, 54429, '94'], [1347517379, 54387, '52'], [1347517411, 54419, '84'], [1347517386, 54394, '59'], [1347517384, 54392, '57'], [1347517374, 54382, '47'], [1347517462, 54470, '135'], [1347517431, 54439, '104'], [1347517419, 54427, '92'], [1347517428, 54436, '101'], [1347517466, 54474, '139'], [1347517443, 54451, '116'], [1347517463, 54471, '136'], [1347517385, 54393, '58'], [1347517387, 54395, '60'], [1347517373, 54381, '46'], [1347517372, 54380, '45'], [1347517418, 54426, '91'], [1347517420, 54428, '93'], [1347517469, 54477, '142]'], [1347517442, 54450, '115'], [1347517408, 54416, '81'], [1347517390, 54398, '63'], [1347517407, 54415, '80'], [1347517429, 54437, '102']]
print("Given array is")
print(seq);
print("\n")
print("Sorted array is")
print(mergesort(seq))
If you chage left[i][0] < right[j][0] to left[i][1] < right[j][1] then it will sort accrding to the second element in the inner array.