using Dates
using Random
gt=0
gt2=0
tic() = (global __t0 = now())
toc() =  (now() - __t0)
A=[25 24 23 22 21;
20 19 18 17 16;
15 14 13 12 11;
10 9 8 7 6;
5 4 3 2 1;]

println("Initial matrix")
println(A)

shuffled = reshape(shuffle(vec(A)), size(A))

println("Shuffled matrix")
println(shuffled)

tic()
sorted_rows = reshape(sort(vec(shuffled), alg=MergeSort), size(shuffled))
println("\nSorted matrix MergeSort:")
A_row = reshape(vec(sorted_rows), 5, 5)'
println(A_row)
println("Elapsed time MergeSort is: ",toc())
toc()

tic()
sorted_rows = reshape(sort(vec(shuffled), alg=InsertionSort), size(shuffled))
println("\nSorted matrix InsertionSort:")
A_row = reshape(vec(sorted_rows), 5, 5)'
println(A_row)
println("Elapsed time InsertionSort is: ", toc())
toc()

tic()
sorted_rows = reshape(sort(vec(shuffled), alg=QuickSort), size(shuffled))
println("\nSorted matrix QuickSort:")
A_row = reshape(vec(sorted_rows), 5, 5)'
println(A_row)
println("Elapsed time QuickSort is: ", toc())
toc()

tic()
println("Let's choose the worst path to traverse all rows and cols to target:")
for i in 2:3        
    for j in 1:5    
        println("A[$i,$j] = ", A_row[i,j])
    end
end
println("Elapsed time of the worst path is: ", toc())
gt1=toc()

tic()
println("Let's choose the shortest path in clustered Dijkstra algorithm:")
for i in 5:-1:1        
    for j in 5:-1:1  
        if i==j
            println("A[$i,$j] = ", A_row[i,j])
        end
    end
end
println("Elapsed time clustered Dijkstra is: ", toc())
gt2=toc()
println("Difference of the best path minus the worst path is ",abs(gt2-gt1))
println("Which is in the worst case for clustered Dijkstra better off ",abs(gt2-gt1)/abs(gt1)*100," %")

slice1=Float64[]
append!(slice1,abs(gt2-gt1)/abs(gt1)*100)

We simply tried timing for the best path and for the worst path in matrix. The clustered Dijkstra path is in avg one third better then traversing through the worst path. The best case is sqrt(2) which is 41% in average per square matrix. We reached in reality 31% improvement per clustered Dijkstra: Simply the worst case scenario path was traversing every node in rectangle manner as we see in code for cycles. Well this imply for GPS navigation in cars one third weaker processor and battery drain is lower for the trips with at least 1000 nodes searched in...

---